Welche neuartigen Datenstrukturen werden in der adaptiven FEM verwendet?

9

Viele adaptive FEM-Bibliotheken verwenden erweiterte Netzdatenstrukturen, um das Hinzufügen / Entfernen von Knoten, Kanten, Dreiecken, Tetraedern usw. zu handhaben. Beispielsweise verwendet die p4est- Bibliothek Octree-Datenstrukturen zur adaptiven Netzverfeinerung . Sie würden nicht oft Oktrees finden, die für Berechnungen in einem statischen Netz verwendet werden.

Was ändert sich auf der Seite der linearen Algebra für die adaptive FEM?

Die unverblümteste Art, die ich mir vorstellen kann, wäre, alle Systemmatrizen vollständig neu zu erstellen, wenn das Netz verfeinert oder vergröbert wird. Wenn die Netzanpassung eine ausreichend seltene Operation ist, werden die Kosten dafür letztendlich über den Rest der Berechnung amortisiert. Mit diesem Ansatz könnte man leicht die vorhandene Software für spärliche lineare Algebra (PETSc, Trilinos usw.) nutzen.

Wird diese stumpfe Methode am häufigsten verwendet, oder gibt es Bibliotheken, die es schaffen, die alte Matrix während der Verfeinerung wiederzuverwenden oder zu ändern? Schließlich bleiben der größte Teil des Netzes und die entsprechenden Matrizen während einer Netzanpassung unverändert.

Daniel Shapero
quelle

Antworten:

6

Ja, der häufigste Ansatz ist der Wiederaufbau. Datenstrukturen, die vor Ort geändert werden können, sind nach dem Einrichten in der Regel weniger effizient, und die Neuzuweisung ist im Vergleich zum Zusammenbau (z. B. aufgrund von Nichtlinearität) recht günstig. Daher ist dies eine gute Lösung. Außerhalb relativ seltener Nischen mit sehr einfachen Lösungen wird Ihre Anwendung durch Versuche, dynamische Datenstrukturen in den Lösern zu verwenden, nur langsamer. Es ist jedoch eine verbreitete Wahrnehmung unter denen, die vergessen, die Leistung zu messen oder zu modellieren.

Jed Brown
quelle
3

Wie Jed bereits sagte, wird die Wiederverwendung von linearen Algebra-Komponenten wie Matrizen und Vektoren normalerweise nicht durchgeführt. Es ist auch nicht notwendig: Das Einrichten dieser Komponenten ist im Vergleich zu den Kosten für das Lösen linearer Systeme vergleichsweise sehr billig.

Wenn Sie nach Dingen suchen, die sich ändern, wenn Sie von statischen zu adaptiv verfeinerten Netzen wechseln, besteht das größte Hindernis darin, Knoten zu hängen. In deal.II wird dies von der ConstraintMatrix- Klasse behandelt, die mehrere 1000 Codezeilen benötigt. Einige der Beschreibungen dieser Klasse finden Sie in der Arbeit von mir und Oliver Kayser-Herold (verlinkt auf meiner Publikationsseite ). Keine andere Komponente (außer natürlich die Handhabung des Netzes) hat so viele Anpassungen erforderlich gemacht, wenn von festen zu adaptiven Netzen gewechselt wurde.

Wolfgang Bangerth
quelle