Multigrid auf "nicht perfekt rechteckigem" Raster

9

Multigrid-Einführungen verwenden normalerweise ein rechteckiges Raster. Die Interpolation von Werten ist dann einfach: Interpolieren Sie einfach linear an der Kante zwischen zwei benachbarten Knoten des Grobgitters, um den Wert des Feingitterknotens an dieser Kante zu ermitteln.

Für eine FEM-Anwendung habe ich ein Gitter, das "topologisch" rechteckig ist, so dass Knotenverbindungen wie in einem rechteckigen Gitter sind. Die Knoten sind jedoch nicht perfekt auf einem Gitter ausgerichtet, sondern können kleine Entfernungen zurücklegen, um die Geometrie besser anzupassen, während die Verbindungen wie in einem perfekten rechteckigen Gitter beibehalten werden.

Das Netz sieht ungefähr so ​​aus: Beispiel Netz . Sie sehen: Verbindungen sind "normal rechteckig", Knotenpositionen jedoch nicht.

Ich kann mir mehrere "vernünftige" geometrische Interpolationsschemata für eine solche Einstellung vorstellen.

Die allgemeine Frage lautet: Benötigt Multigrid ein perfekt ausgerichtetes rechteckiges Gitter oder funktioniert es auch mit der oben beschriebenen Situation, solange die Interpolation "gut" ist? Oder ist es in diesem Fall besser, algebraisches Multigrid zu verwenden? (Was ich nicht bevorzuge, da es nicht so intuitiv ist wie geometrisches Multigrid.)

Michael
quelle
Ich bin mir nicht sicher, ob ich verstehe, was Sie damit meinen, dass das Gitter topologisch rechteckig ist, aber wo die Knoten nicht wie in einem rechteckigen Gitter ausgerichtet sind. Ist das Gitter ein strukturiertes rechteckiges Gitter? Könnten Sie dies bitte klarstellen, vielleicht mit einer Zeichnung? Ist das Problem, dass Sie rechteckige Elemente verwenden, die nicht wie bei Verwendung eines strukturierten kartesischen Gitters ausgerichtet sind?
James
@James, ich interpretierte die Frage von OP eher wie folgt: "Was passiert, wenn ich ein 'kartesisches' Gitter in einem Trapez habe?".
Bill Barth

Antworten:

6

Multigrid benötigt kein kartesisches (rechteckiges), einheitliches Gitter. Sie müssen eine feine und eine grobe Ebene definieren (möglicherweise rekursiv, wenn Sie von einem zweistufigen zu einem mehrstufigen Schema wechseln möchten) und Interpolationsoperatoren zwischen diesen Ebenen definieren. Der einfachste Weg, dies zu erklären, ist, wenn Sie tatsächlich ein kartesisches Gitter haben, aber Sie können tatsächlich mit jedem groben Netz beginnen, es einmal verfeinern und einfach so: Sie haben ein feineres Netz.

Mit anderen Worten, es ist am einfachsten, sich Multigrid-geeignete Netze nicht als feines Netz vorzustellen und die gröberen Netze zu finden, sondern mit einem groben Netz zu beginnen, aus dem Sie durch gleichmäßige Verfeinerung die feineren Ebenen erhalten (dh jedes Viereck ist unterteilt in vier kleinere). Da eine einheitliche Verfeinerung immer möglich ist, erhalten Sie leicht eine Hierarchie. Dies steht im Gegensatz zur Vergröberung, die nicht immer möglich ist, wenn Sie nur ein bestimmtes Netz erhalten, und das Definieren einer Netzhierarchie erheblich erschwert. (Aus diesem Grund haben die Leute algebraische Multigrid-Methoden entwickelt, um die Grobebenen basierend auf der Matrix zu definieren, ohne an das zugrunde liegende Netz zu denken, aus dem sie erstellt wurden.)

Wolfgang Bangerth
quelle
Ich habe ein Bildbeispiel in die Frage bearbeitet. Ich würde annehmen, dass die Vergröberung in meinem Fall extrem einfach ist, indem nur jeder zweite Knoten (pro Dimension) genommen und die FEM für dieses Gitter neu berechnet wird, um die grobe Matrix / den groben Operator zu erhalten. Der grobe Datenvektor kann erhalten werden, indem nur jeder zweite Knotenwert genommen wird.
Michael
1
Das kann oder kann nicht so gut funktionieren, wie Sie wollen (ich nehme an, es wird wahrscheinlich, aber ich bin nicht ganz sicher). Die Sache ist, dass in Ihrem Beispiel die Grobnetzzellen nicht den gleichen Bereich wie die untergeordneten Zellen abdecken und daher keine Verschachtelungseigenschaft der Finite-Elemente-Räume vorhanden ist: Die Funktionen, die Sie auf dem Grobnetz darstellen können, sind keine Teilmenge von die Funktionen, die Sie auf dem feinen Netz darstellen können. Joe Pasciak und Jim Bramble haben Papiere zu solchen Fällen geschrieben, und ich denke, ich erinnere mich, dass sie zum Arbeiten gebracht werden können. Aber es ist mir nicht sofort klar.
Wolfgang Bangerth
4

Nehmen wir an, Sie haben das folgende Raster aus rechteckigen Elementen:

Geben Sie hier die Bildbeschreibung ein

Wenn Sie nun Ihre Interpolation unter der Annahme eines normal strukturierten rechteckigen Gitters durchführen, werden Sie Fehler einführen, die mit dieser ungenauen Interpolation verbunden sind. Mit anderen Worten, wenn Sie Ihren Restvektor einschränken und Ihren Fehlervektor verlängern, treten Fehler bei der Interpolation auf.

Wenn Ihr Raster einem normalen strukturierten kartesischen Raster "nahe" ist, kann dies zumindest zunächst funktionieren, aber ich vermute, dass eines von zwei Dingen passieren wird, je nachdem, wie weit Ihr Raster von der Rechteckigkeit entfernt ist:

1) Möglicherweise stellen Sie fest, dass das Multigrid zunächst konvergiert. Schließlich ist Ihr Fehler anfangs sowieso groß und Ihre "ungefähre" Interpolation bedeutet wirklich nur, dass einige Knoten leicht überrepräsentiert sind, während andere leicht unterrepräsentiert sind. Möglicherweise stagniert die Konvergenz jedoch, wenn die Lösung genauer wird und die Interpolationsfehler wichtiger werden.

2) Eine andere Möglichkeit besteht darin, dass das Multigrid zwar konvergiert, jedoch nicht so schnell wie es sollte, wenn Sie die richtige Interpolation verwendet haben.

Grundsätzlich gewichten Sie die Wichtigkeit bestimmter Knoten ungenau, indem Sie Ihre Interpolation deaktivieren. Zum Beispiel in 2D, wenn Sie einen bestimmten Knoten wie folgt gewichten:

[0,250,50,250,51.00,50,250,50,25]]

wenn in Wahrheit, weil Ihr Gitter nicht genau kartesisch ist, sollte es sein:

[0,250,550,250,551.00,490,280,520,30]]

dann führt dies zu einem Fehler. Ob dieser Fehler die Konvergenz verhindert, hängt wahrscheinlich davon ab, wie weit Ihr Raster davon entfernt ist, kartesisch zu sein.

Obwohl AMG schwieriger zu verstehen / zu implementieren ist, scheint es die richtige Methode für Ihr Grid zu sein. Das Anwenden von geometrischem Multigrid auf ein "ungefähres" rechteckiges Gitter mag funktionieren, aber ich würde vermuten, dass es bestenfalls eine Pflasterlösung ist. Hoffe das hilft.

Update : Ich glaube, meine Antwort war verwirrend. Ich sage nicht, dass geometrisches Multigrid nur mit kartesischen Netzen funktioniert, sondern dass das Definieren der Interpolation (und damit der Einschränkung) von kartesischen Netzen einfach ist, während dies bei nicht strukturierten Netzen schwierig sein kann. Betrachten Sie beispielsweise den Fall einer einfachen 2D-Domäne mit einem Dreiecksnetz. Das Verfeinern dieses Netzes ist - zumindest konzeptionell - einfach, aber wie würden Sie einen Interpolationsoperator zwischen dem groben und dem feinen Netz definieren? Ich bevorzuge AMG einfach, weil es eher wie ein "Black-Box" -Löser funktioniert, dh keine Informationen über das zugrunde liegende Netz benötigt, dies ist jedoch nur meine persönliche Voreingenommenheit / Eigenart. Geometrisches Multigrid kann funktionieren, solange Sie genaue Interpolationsoperatoren bereitstellen können.

James
quelle
Ich kann dies als "hängt davon ab, wie gut Ihre Interpolation ist" lesen, richtig? Wenn ich also ein "perfektes" Interpolationsschema finden kann, sollte es mir gut gehen?
Michael
1
Ich denke, diese Antwort ist wahr, aber irreführend - sie besagt, dass Sie die falsche Antwort erhalten, wenn Sie so tun, als wäre Ihr Raster normal kartesisch, wenn dies nicht der Fall ist. Das stimmt, aber man könnte das Gleiche über jede numerische Methode sagen. Der Punkt ist, dass geometrisches Multigrid bei allgemeiner Implementierung auf allgemeineren Netzen genau ist .
David Ketcheson
Ich bin damit einverstanden, dass geometrisches Multigrid mit nicht kartesischen Netzen verwendet werden kann, solange dies korrekt durchgeführt wird. Ich habe gerade die OP-Frage als die Frage verstanden, ob die Verwendung eines "ungefähr" kartesischen Netzes während der Verwendung einer Interpolation, die für ein tatsächliches kartesisches Netz ausgelegt ist, funktionieren würde.
James
@Michael Grundsätzlich benötigen Sie eine Möglichkeit, Interpolationsoperatoren zwischen verschiedenen Rasterebenen zu definieren. Mit kartesischen Maschen ist dies einfach. Bei nicht kartesischen Netzen kann dies schnell schwieriger werden, je nachdem, wie unstrukturiert Ihre Netze sind. Wie Wolfgang in seiner Antwort sagt, können Sie aus einem groben Netz immer ein verfeinertes Netz erstellen, aber es kann schwierig sein, sinnvolle Interpolationsoperatoren zu definieren. Der Vorteil von AMG besteht darin, dass es sich eher wie ein "Black-Box" -Löser verhält, da Sie keine Netzdaten benötigen, um Interpolationsoperatoren zu definieren. Alles was Sie brauchen ist die Matrix
James
@MIchael Also um deine Frage zu beantworten. Ja, wenn Sie genaue Interpolationsoperatoren finden können, funktioniert das geometrische Multigrid einwandfrei. Hoffe das hilft.
James