A review of algebraic multigrid

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 einen Überblick über den ersten hierarchischen, rein matrix-orientierten Verfahrensansatz, die algebraische Mehrgittermethode (AMG). AMG kann, zum Beispiel, unmittelbar zur Lösung verschiedener Typen elliptischer partieller Differentialgleichungen auf unstrukturierten, zwei- oder dreidimensionalen Gittern eingesetzt werden. Weil AMG keine geometrische Information ausnutzt, ist es ein "black-box" Löser, der unmittelbar auch zur Lösung von Problemen eingesetzt werden kann, die keinen direkten geometrischen Hintergrund besitzen, vorausgesetzt, die zugrundeliegenden Matrizen erfüllen gewisse Voraussetzungen.

Since the early nineties, there has been a strongly increasing demand for more efficient methods to solve large sparse, 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. This paper gives a review of the first hierarchical and purely matrix-based approach, algebraic multigrid (AMG). AMG can directly be applied, for instance, to efficiently 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 matrices have certain properties.