Mehrgitter-Verfahren

Mehrgitterverfahren bilden in der numerischen Mathematik eine effiziente Klasse von Algorithmen zur näherungsweisen Lösung von Gleichungssystemen, die aus der Diskretisierung partieller Differentialgleichungen stammen. Elliptische Probleme wie die Poisson-Gleichung können damit bei n Unbekannten mit einem Rechenaufwand von der Ordnung O(N) gelöst werden. Die Konvergenzordnung ist dabei nicht von der Feinheit der Gitter abhängig. Mehrgitterverfahren sind in dieser Hinsicht "optimal". Die wesentliche Alternative zu Mehrgitterverfahren sind vorkonditionierte Krylow-Unterraum-Verfahren.

Beschreibung

Die Grundidee ist, dass eine Hierarchie von gröber werdenden Gittern aufgebaut wird. Diese werden genutzt, um eine Approximation des unbekannten Fehlers einer Anfangsnäherung der Lösung zu berechnen.

Zunächst sei auf dem feinsten Gitter ein lineares Gleichungssystem A_lx = b_l mit regulärer Matrix $A_l \in \mathbb{R}^{n \times n}$ gegeben. Auf die Näherung $x_l^k$ wird dann als erstes ein Glätter S angewandt, der hochfrequente Fehleranteile dämpft, wodurch ein glatter Fehler entsteht. Was ein sinnvoller Glätter ist, hängt davon ab welche partielle Differentialgleichung gelöst werden soll. Für viele sind Gauß-Seidel- oder Jacobi-Relaxation geeignet. Das zugehörige Residuum $r_l=b_l-A_lSx_l^k$ wird auf das nächstgröbere Gitter restringiert: r_{l − 1} = Rr_l. Da niederfrequente Fehleranteile auf feinen Gittern hochfrequenten Fehleranteilen auf gröberen Gittern entsprechen, ergibt sich mit der Residuumsgleichung A_{l − 1}e = r_{l − 1} ein Problem mit ähnlicher Struktur wie das Ursprungsproblem, allerdings mit kleinerer Dimension.

V-Zyklus

W-Zyklus

Dies wird rekursiv bis zum gröbsten Gitter wiederholt (V-Zyklus), wo das Gleichungssystem direkt gelöst werden kann. Der berechnete Fehler wird dann sukzessive mittels Prolongation P auf die feineren Gitter rückprolongiert und geglättet. Schließlich wird mit der Fehlerapproximation auf dem feinsten Gitter die ursprüngliche Näherung der Lösung korrigiert.

Dies funktioniert bei einem linearen Problem Ax = b mit Lösung x ^* , da dann der Fehler e = x^k − x ^* der Näherungslösung x^k über die Residuumsgleichung Ae = r = Ax^k − b berechnet werden kann. Auf ein nichtlineares Problem L(u) = f lässt sich dies nicht direkt übertragen, da hier die Residuumsgleichung L(e) = r gar nicht lösbar sein muss. Deswegen löst man da auf dem groben Gitter statt dessen L(u + e) = L(u) + r, was im linearen Fall äquivalent wäre.

Der Einsatz der groben Gitter beschleunigt die Informationsausbreitung über dem Diskretisierungsgebiet. Die Kombination von Grobgitterkorrektur und Glätter ergibt eine schnelle, maschenweitenunabhängige Konvergenzrate.

Mehrgitterverfahren können die Norm des Fehlers für das Poisson-Problem in einem V-Zyklus um mehr als den Faktor 10 reduzieren, sind hier also äußerst effektiv.

Trotz ihrer Optimalität sind Mehrgitterverfahren im industriellen Sektor momentan nur spärlich verbreitet. Gründe hierfür sind:

• Die Verfahren sind noch "relativ" jung.
• Mehrgitterverfahren sind schwierig zu implementieren. Grobe Gitter, Prolongations- und Restriktionsoperatoren müssen sorgfältig abgestimmt werden auf
  • die Gestalt des Diskretisierungsgebietes.
  • die diskretisierte Differentialgleichung.
• Aufgrund ihrer Natur (Zugriff auf alternierend feinere und gröbere Gitter) führen Mehrgitterverfahren
  • zu vielen Cache-Misses (bei lexikographischer Knotennummerierung),
  • und sind schwer zu parallelisieren.

Geschichte

Die frühesten Arbeiten zu Mehrgitterverfahren stammen von den sowjetischen Mathematikern Fedorenko und Bakhvalov aus den frühen 60er Jahren. Bekannt wurden sie im Wesentlichen durch die Arbeiten von Wolfgang Hackbusch in den späten 1970er Jahren, der auch wichtige Konvergenzresultate erzielte. Ein weiterer Mehrgitterpionier ist Achi Brandt: er behauptet, jede partielle Differentialgleichung sei durch Mehrgitterverfahren effizient und schnell lösbar.

Verwandte Verfahren

Bei komplexen Geometrien erreichen Mehrgitterverfahren schnell ihre Grenzen. Als Alternative wurden algebraische Mehrgitterverfahren entwickelt, die rein auf Modifikationen der Gleichungssysteme beruhen und keine speziellen geometrischen Eigenschaften wie Änderungen der Gitterweite benutzen. Generell sind Multilevel-Verfahren von Mehrgitter inspiriert.

Für Probleme mit großen Skalenunterschieden (beispielsweise turbulenten Strömungen: Wirbel im Bereich von μm, normale Geometrien im Bereich von Metern) gibt es in jüngerer Zeit (etwa seit 1995) Ansätze, die physikalischen Vorgänge auf den verschiedenen Skalen durch verschiedene numerische Ansätze zu lösen. Dies wird auch als Mehrskalenansatz bezeichnet und ist mit dem Mehrgitterverfahren eng verwandt.

In der Signalverarbeitung gibt es die Gauß-Laplace-Pyramide für eine Mehrgittertechnik .

Literatur

• William L. Briggs, Van Emden Henson, and Steve F. McCormick, A Multigrid Tutorial, Second Edition, SIAM, 2000 (book home page), ISBN 0-89871-462-1
• Wolfgang Hackbusch: Multigrid Methods and Applications, Springer, 1985
• Pieter Wesseling: An Introduction to Multigrid Methods, Corrected Reprint. Philadelphia: R.T. Edwards, Inc., 2004. ISBN 1-930217-08-0