Algebraisches Mehrgitterverfahren

Das Algebraische Mehrgitterverfahren (AMG) ist ein numerisches Verfahren zur Lösung von linearen Gleichungssystemen $Ax=b$ mit $A\in \mathbb {R} ^{n\times n}$, die beispielsweise aus der Diskretisierung von elliptischen partiellen Differentialgleichungen stammen kann. Es stellt eine Modifikation klassischer Mehrgitterverfahren dar.

Unterschiede zum herkömmlichen Mehrgitterverfahren

Der wesentliche Unterschied zum herkömmlichen Mehrgitterverfahren besteht darin, dass es direkt auf lineare Gleichungssysteme angewendet werden kann, ohne geometrische Eigenschaften zu benutzen.

Die grundlegenden Bausteine wie Glätter und Gitteroperatoren gibt es ebenfalls bei AMG, die Konzepte werden jedoch anders umgesetzt: So werden die Gitter durch Teilgraphen der Matrix ersetzt. Die Glätter werden bereits im Voraus gewählt, der Interpolations- bzw. Restriktionsoperator muss erst konstruiert werden (im Unterschied zum gewöhnlichen Mehrgitterverfahren).

AMG benötigt eine Vorbereitungsphase zur Berechnung gröberer Gitter und Interpolationsoperatoren, sodass es im Vergleich zum klassischen Mehrgitterverfahren meistens langsamer ist. Jedoch liegt der Hauptnutzen von AMG darin, dass Probleme behandelt werden können, die mit klassischen Mehrgitterverfahren nicht gut zu lösen sind.

Betrachtete Probleme

AMG zielt beispielsweise auf Probleme mit komplizierten Geometrien, bei denen klassische Mehrgitterverfahren nur schwer anwendbar sind. So kann es dann schwer oder unmöglich sein, gröbere Gitter zu finden. AMG hat dieses Problem nicht, da die Vergröberung anders definiert ist und keinen geometrischen Hintergrund hat.

Auch kann ein gegebener Interpolationsoperator schlechte Resultate liefern, da die Interpolation in AMG jedoch gewählt wird, liefert dieses Verfahren ebenfalls bessere Ergebnisse. Des Weiteren lassen sich mit AMG natürlich auch Probleme lösen, die überhaupt nicht geometrisch motiviert sind.

Literatur

• William L. Briggs, Van Emden Henson und Steve F. McCormick: A Multigrid Tutorial, 2. Auflage, SIAM, 2000, ISBN 0-89871-462-1
• Stephen F. McCormick: Multigrid Methods, SIAM, 1987, ISBN 0-89871-214-9