Mehrgitterverfahren

Mehrgitterverfahren bilden eine Klasse von Algorithmen und Methoden zur effizienten Lösung von Gleichungssystemen mehrdimensionaler Probleme in der numerischen Mathematik. Partielle Differentialgleichungen wie die Poisson-Gleichung können damit mit einem Rechenaufwand von der Ordnung \(\displaystyle O(N)\) mit \(\displaystyle N\) der Anzahl der Unbekannten gelöst werden. Mehrgitterverfahren sind also "optimal".
Die Grundidee ist dabei, dass man die Auflösung des Gitters in einer Hierarchie von Ebenen immer weiter vergröbert und somit auch die Problemgröße reduziert. Auf den groben Gittern werden aber jeweils nur Korrekturen der Fehler auf den feineren Gitter mittels Glättern (Gauß-Seidel oder Jakobi Relaxation) angenähert und anschließend aufaddiert. Hochfrequente Fehleranteile werden durch diese Prozedur schnell gedämpft. Der Fehler wird also sehr schnell glatt. Niederfrequente Fehleranteile auf den feinen Gittern werden dabei zu hochfrequenten Fehlernanteilen auf gröberen Gittern, die die Glätter schnell reduzieren können.
Der Einsatz der groben Gitter beschleunigt die Informationsausbreitung über dem Diskretisierungsgebiet. Die Kombination von Grobgitterkorrektur und Glätter ergibt eine schnelle, maschenweitenunabhängige Konvergenzrate.
Ein normaler Mehrgitterzyklus (oder V-Zyklus) beginnt auf dem feinsten Gitter mit einer Näherung der Lösung. Mit dieser meist falschen Lösung wird die Residuumsgleichung aufgestellt. Dieses neue Gleichungssystem wird durch eine Restriktion auf die Dimension des nächstgröberen Gitters überführt. Dann wird dieses Verfahren rekursiv bis zur gröbsten Mehrgitter Ebene durchgeführt, wo das Gleichungssystem meist direkt gelöst wird. Beim Zurückkehren werden die Korrekturen durch Prolongation (meist Interpolation) auf die feinere Ebene überführt und dann zur dortigen Näherung aufaddiert. Auf dem feinsten Gitter angelangt ist ein V-Zyklus abgeschlossen.
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.
 
 

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.
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
  • 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.

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.
Für Probleme mit großen Skalenunterschieden (beispielsweise turbulente Strömungen: Wirbel im Bereich von \(\displaystyle \mu 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. Ein Beispiel für ein solches Verfahren ist die heterogene Mehrskalenmethode (engl.: The Heterogeneous Multiscale Method), entwickelt von Weinan E, Bjorn Enquist und anderen.

Ich stimme mit der Mathematik nicht überein. Ich meine, daß die Summe von Nullen eine gefährliche Zahl ist.

Stanislaw Jerzy Lec

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Mehrgitterverfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе