AMGe: a theory for a new generation AMG for finite element discretizations

Robert Falgout

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


Multigrid, to be successful, requires that those error components not reduced effectively by the relaxation scheme be reduced by the coarse-grid correction. Historically, in geometric multigrid, applied to elliptic problems, the observation is made that the error components not reduced by relaxation are physically smooth, and can therefore be represented accurately on a coarse grid. This smoothness also allows accurate interpolation by low-order operators.

For algebraic multigrid (AMG), however, there is no "grid" and the physical concepts of "smoothness" and "coarse-grid" have no meaning. Classic AMG defines smooth components as those for which relaxation is ineffective, i.e., vectors whose residual is small compared to the size of the vector itself. These components correspond to the eigenvectors, associated with the smallest eigenvalues, of the operator matrix. Hence the coefficients of the operator matrix can be used to select a set of variables, or "points," that can represent these smooth components. Interpolation formulas are then constructed to accurately represent these components.

While this method works very well on certain classes of problems, it does not work well for some particularly important problems, such as thin-body elasticity problems. A fundamental difficulty is that the interpolation operators are local, and yet must accurately represent, locally, the global smooth functions. But the nature of these functions is not apparent, as it is in the geometric case.

AMGe is a new theory developed to address this difficulty. Essentially, AMGe depends on a local version of a well-known global convergence theory. In the theory, a local version of the operator matrix is created by summing the local stiffness matrices for the elements having the target point as a node. By solving a certain optimization problem one can effectively determine the optimal interpolation operator to represent the appropriate eigenfunctions of the local operator. Further, the theory gives a measure of the quality, not only of the interpolation, but also of the choice of the coarse grid equations.

In this talk we outline the theory of the AMGe interpolation, describe its historical derivation, and contrast it with other approaches to overcoming the algebraic interpolation problem. We describe how this approach can be used to select coarse grid points and to measure their value. Finally, we indicate the results of experimentation using this theory and describe the steps necessary to produce an effective code.