Algebraic multigrid (AMG). An introduction with applications
Klaus Stüben
Abstract
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.