Algebraic multigrid (AMG). An introduction with applications
Klaus Stüben · Fraunhofer-Publica (Fraunhofer-Gesellschaft) · 2022
Seit den frühen neunziger Jahren besteht ein stark wachsender Bedarf an effizienteren Methoden zur Lösung großer, dünnbesetzter und unstrukturierter linearer Gleichungssysteme. Klassische Lösungsverfahren sind für praktisch relevante Problemgrößen an ihre Grenzen gestoßen und neue hierarchische Verfahren mußten entwickelt werden, um die numerische Effizienz zu steigern. Dieses Paper gibt eine elementare Einführung in die erste, rein matrix-orientierte Methode dieser Art, die algebraische Mehrgittermethode (AMG). In dieser Methode wird die klassische Mehrgitteridee der Kombination von Glättungs- mit Grobgitterkorrekturprozessen auf gewisse Klassen von Matrixproblemen übertragen. Neben ihrer Robustheit und Effizienz besteht ein großer Vorteil dieser Methode etwa in ihrer direkten Anwendbarkeit zur Lösung verschiedener Typen elliptischer partieller Differentialgleichungen auf unstrukturierten, zwei- oder dreidimensionalen Gittern. Weil AMG keine geometrische Information ausnutzt, kann es unmittelbar auch zur Lösung von Problemen eingesetzt werden, die keinen direkten geometrischen Hintergrund besitzen, vorausgesetzt, die zugrundeliegenden Matrizen erfüllen gewisse Voraussetzungen. Obwohl der AMG-Ansatz bereits zu Beginn der achtziger Jahre entwickelt wurde, stellt er immer noch einen der effizientesten Ansätze zur algebraischen Lösung entsprechender Probleme dar. Allerdings sind zwischenzeitlich einige Modifikationen und Erweiterungen hinzugekommen. Neben einer Einführung in die theoretischen Grundlagen von AMG beschreiben wir einen konkreten Algorithmus und demonstrieren seine Robustheit und Effizienz am Beispiel verschiedener Anwendungen.