Wie konstruiere ich einen Verlängerungs- und Restriktionsoperator für einen algebraischen Multigrid-Löser?

10

Ich versuche, ein lineares Gleichungssystem zu lösen, das spärlich ist, aber keine Bandstruktur aufweist. Ich habe gehört, dass es eine Möglichkeit gibt, die Prinzipien eines Multigrid-Lösers für implizite Finite-Differenzen-Schemata auf ein allgemeines lineares Problem auszudehnen (wenn ich mich nicht irre, nennt man das algebraischen Multigrid-Löser). Nachdem ich einige Literatur darüber gelesen habe, bin ich immer noch sehr verwirrt darüber, wie man zwischen groben und feinen Gittern interpoliert (dh verlängert und einschränkt), ohne die schöne Struktur der gebänderten Matrizen wie bei einem Finite-Differenzen-Schema auszunutzen. Gibt es eine Heuristik? Kann jemand ein Beispiel geben?

linear-algebra multigrid Paul
quelle

Antworten:

13

Erstens, wenn Sie ein strukturiertes Gitter haben, möchten Sie möglicherweise geometrisches anstelle von algebraischem Multigrid verwenden, da einige theoretische und Effizienzvorteile bestehen (z. B. die Möglichkeit zur Rediskretisierung anstelle der Verwendung von Galerkin-Grobgitteroperatoren). Algebraische Multigrid-Methoden fallen im Allgemeinen in zwei Kategorien.

Klassisches algebraisches Multigrid

M

Glättete Aggregation

ATA(ebenfalls von Mark Adams, meistens ein vollständiger Ersatz für Prometheus) und die geglättete Aggregationskomponente des CUDA-basierten GPU-Codes CUSP .

Beachten Sie, dass auf alle oben genannten Programme über eine gemeinsame Schnittstelle mit PETSc zugegriffen werden kann .

Jed Brown
quelle
4

"Multigrid" von Trottenberg et al. Ist ein ausgezeichnetes Buch und es sieht so aus, als ob das meiste davon in Google-Büchern verfügbar ist. Es enthält einen Anhang zu AMG, und Sie müssen wahrscheinlich einige Hintergrundinformationen zu MG aus dem Rest des Buches erhalten. "Ein Multigrid-Tutorial" ist auch ein gutes Buch.

Adams
quelle
3

Ich würde Kapitel 8 von "A Multigrid Tutorial" (2Ed) von WL Briggs, VE Henson und SF McCormick vorschlagen. Es gibt einen allgemeinen Überblick über einige wichtige Konzepte wie algebraische Glätte und starke Abhängigkeit. Außerdem wird erläutert, wie der Interpolationsoperator (auch der Grobgitteroperator) definiert und das Grobgitter ausgewählt wird.

Bernardo MR
quelle
Bernardo, willkommen bei scicomp! Ihr zweiter Absatz sieht eher nach einer Frage als nach einer Antwort aus. Könnten Sie es bitte aus Ihrer Antwort herausschneiden und in eine separate Frage einfügen? Die Frage, die Sie in Ihrem zweiten Absatz stellen, ist ein gutes Beispiel für die Art der Frage, die wir gerne sehen scicomp.
Geoff Oxberry