Mehrgitterverfahren

Mehrgitterverfahren beschleunigen die Lösung diskretisierter partieller Differentialgleichungen (PDG), indem sie kostengünstige Glättung auf feinen Gittern mit Korrekturen kombinieren, die auf gröberen Gittern berechnet werden. Dadurch wird der Fehler auf jeder Längenskala angegangen und Konvergenzraten erzielt, die unabhängig von der Maschenweite sind.

Definition

Ein Mehrgitterverfahren ist ein iterativer Löser, der den Fehler auf einer Hierarchie von Gittern unterschiedlicher Auflösung darstellt. Dabei werden kostengünstige Relaxationen zur Entfernung oszillierender Fehlerkomponenten auf feinen Gittern und Grobgitterlösungen zur Entfernung glatter Komponenten rekursiv über alle Skalen hinweg eingesetzt.

Scope

Dieses Thema behandelt die Glättungseigenschaft einfacher Iterationen, die Übertragung von Residuen und Korrekturen zwischen Gittern durch Restriktion und Prolongation, die Zwei-Gitter- sowie V-, W- und Full-Multigrid-Zyklen, geometrische versus algebraische Mehrgitterverfahren und die optimale (lineare) Rechenkomplexität, die Mehrgitterverfahren zu einem Benchmark-Löser für elliptische Probleme macht.

Core questions

• Warum reduzieren einfache Iterationen oszillierende Fehler schnell, aber glatte Fehler langsam, was die Verwendung von Grobgittern motiviert?
• Wie werden Residuen auf Grobgitter restringiert und Korrekturen auf Feingitter zurückprolongiert?
• Wie kombinieren Mehrgitterzyklen diese Operationen, um eine maschenunabhängige Konvergenz zu erreichen?
• Wie erweitert das algebraische Mehrgitterverfahren die Idee auf Probleme ohne zugrunde liegendes geometrisches Gitter?

Key theories

Glättung und Grobgitterkorrektur

Klassische Relaxationsverfahren wie Gauss-Seidel dämpfen hochfrequente (oszillierende) Fehler schnell, beeinflussen aber niederfrequente Fehler kaum; Mehrgitterverfahren nutzen dies aus, indem sie den glatten, langsam konvergierenden Fehler auf gröbere Gitter übertragen, wo er oszillierend erscheint und kostengünstig reduziert wird.

Maschenunabhängige optimale Komplexität

Die rekursive Anwendung von Glättung und Grobgitterkorrektur in V- oder W-Zyklen führt zu Konvergenzfaktoren, die unabhängig von der Gittergröße begrenzt sind, sodass der Aufwand zur Lösung bis zu einer festen Toleranz nur linear mit der Anzahl der Unbekannten wächst.

Mechanisms

Ein Mehrgitterzyklus beginnt mit der Relaxation des Systems auf dem feinen Gitter, um den Fehler zu glätten. Anschließend wird das Residuum berechnet und auf ein gröberes Gitter restringiert, wo die Residuumsgleichung (rekursiv, durch denselben Zyklus) gelöst wird. Die Grobgitterkorrektur wird dann zurückprolongiert und zur Feingitterapproximation addiert, gefolgt von weiterer Relaxation. Da jede Gitterebene die Fehlerkomponenten behandelt, für die sie am effizientesten ist, reduziert der kombinierte Zyklus den Fehler über alle Skalen hinweg in einer festen Anzahl von Durchläufen. Algebraische Mehrgitterverfahren konstruieren die Gitterhierarchie und die Transferoperatoren direkt aus den Matrixeinträgen, sodass kein geometrisches Gitter erforderlich ist.

Clinical relevance

Mehrgitterverfahren gehören zu den effizientesten Lösern für die großen dünnbesetzten Systeme, die aus elliptischen und parabolischen partiellen Differentialgleichungen entstehen. Sie werden als Löser oder als Vorkonditionierer in der numerischen Strömungsmechanik, Strukturmechanik, Elektromagnetik und Bildverarbeitung eingesetzt; ihre nahezu optimale Skalierung ist essenziell für Simulationen extremen Umfangs auf parallelen Supercomputern.

History

Die Mehrgitteridee wurde um 1961 von Fedorenko eingeführt und in den 1970er Jahren von Achi Brandt zu einer praktischen, breit anwendbaren Methode entwickelt; Hackbusch's Analyse stellte sie auf eine rigorose Grundlage, und algebraische Mehrgitterverfahren erweiterten später ihren Anwendungsbereich auf unstrukturierte und nicht-geometrische Probleme, wodurch ihr Status als Löser optimaler Komplexität gefestigt wurde.

Key figures

• Radii Fedorenko
• Achi Brandt
• Wolfgang Hackbusch
• Stephen McCormick

Seminal works

• trottenberg2001
• briggs2000

Frequently asked questions

Warum sind Grobgitter überhaupt hilfreich?

Glatte Fehler, die eine Feingitterrelaxation nur langsam entfernt, erscheinen auf einem gröberen Gitter oszillierend, wo die Relaxation sie schnell und kostengünstig beseitigt. Das Durchlaufen von Gittern unterschiedlicher Auflösung eliminiert somit jede Fehlerkomponente effizient.

Was ist der Unterschied zwischen geometrischen und algebraischen Mehrgitterverfahren?

Geometrische Mehrgitterverfahren verwenden eine explizite Hierarchie gröberer Gitter aus der Problemgeometrie, während algebraische Mehrgitterverfahren die groben Ebenen und Transferoperatoren automatisch aus der Matrix konstruieren, wodurch sie anwendbar sind, wenn keine natürliche Gitterhierarchie existiert.