Algebraic Multigrid: Theory and Practice

Van Emden Henson

Center for Applied Scientific Computing
Lawrence Livermore National Laboratory
PO Box 808, L-560
Livermore, CA 94551

In recent years Algebraic Multigrid (AMG) methods have received a great deal of attention. Principally, this is due to the trend toward extremely large problems posed on unstructured grids. This trend will certainly continue for some time, and AMG seems a natural approach to dealing with such problems.

But what, exactly, is AMG? In fact, it describes a family of algorithms, related only by the fact that they use the algebraic properties of the operator matrix (or, more recently, of the elemental stiffness matrices) to select a smaller system of equations, or coarse "grid," that is used in a two-grid solution cycle. Recursion brings multigrid.

How the sets of coarse equations is selected, and how the transfer operators and coarse version of the original operator are selected gives an AMG method its particular identity.

In this talk we give an overview of AMG methods, describing the fundamental choices that must be made to build an algorithm, and describing some of the methods that are used to make these choices. The details of the classic AMG algorithm of Ruge and Stuben [1] are described, and contrasted with other approaches.

Details of the implementations of AMG are described to provide a foundation for later speakers.

J. W. Ruge and K. Stuben, Algebraic Multigrid, in Multigrid Methods, Stephen F. McCormick, Ed., SIAM, 1987, pp 73-130.