Algebraic multigrid (AMG). An introduction with applications

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.

Since the early nineties, there has been a strongly increasing demand for more efficient methods to solve large sparse and unstructured linear systems of equations. For practically relevant problem sizes, classical one-level methods had already reached their limits and new hierarchical algorithms had to be developed in order to allow an efficient solution of even larger problems. The purpose of this paper is to give an elementary introduction to the first hierarchical and purely matrix-based approach, algebraic multigrid (AMG). The main idea behind AMG is to extend the classical ideas of geometric multigrid (smoothing and coarse-grid correction) to certain classes of algebraic systems of equations. Besides its robustness and efficiency, the main practical advantage of AMG is that it can directly be applied, for instance, to solve various types of elliptic partial differential equations discretized on unstructured meshes, both in 2D and 3D. Since AMG does not make use of any geometric information, it is a \plug-in" solver which can even be applied to problems without any geometric background, provided that the underlying matrix satisfies certain properties. Although the development of AMG goes back to the early eighties, it still provides one of the most efficient algebraic methods to solve corresponding problems. Compared to the original approach, however, several modifications and extensions have been introduced. In addition to the theoretical basics of AMG, we present a concrete algorithm in some detail and demonstrate its robustness and efficiency by means of a variety of typical applications.