AMGe and Element-free AMGe: General algorithms for computing interpolation weights

Van Emden Henson (speaker) and Panayot S. Vassilevski

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


We propose a new algorithm for constructing the interpolation weights in algebraic multigrid (AMG). The rule we propose is related to the interpolation described in [1] for AMGe, an element-based algebraic multigrid. There, the interpolation is based on an energy-minimization principle for finite element applications.

We first review the classical algorithm for constructing interpolation weights in AMG, examining it from an energy-minimization perspective. Our purpose is to extend the classical algorithm in a more general setting than is possible for the traditional M-matrix applications of classical AMG. Next we examine the interpolation rule for AMGe, describing how it is related to the AMG rule and how it is derived as an energy minimization. However, in the AMGe method, as outlined in [1], applying the interpolation rule requires access to the entries of the individual element stiffness matrices. Further, these element matrices must be built on all coarse levels, which is a non-trivial and expensive task [2].

We propose an approach that does not require access to the element matrices even on the fine-grid. However, the additional information we require instead is knowledge of the so-called rigid body modes, that is, the vectors that span the null-space of the global (assembled) Neumann-type matrix. In the simplest case of scalar elliptic PDE discretization matrices, this is just the constant vector. For the elasticity problem, this comprises certain linear functions, which, in practice, means that one needs the coordinates of the fine-grid nodes. In some cases this information may not be available; we use only constant vectors for these cases.

Based on the rigid body modes, we specify appropriate boundary conditions which are imposed on a local neighborhood matrix associated with a fine degree of freedom. This produces a sort of Neumann-type local (or element) matrix. Finally, we can simply apply the rule from the AMGe methods based on the Neumann local matrix.

Some numerical results are given, illustrating the application of the method on discretized elliptic problems.


  1. M. Brezina, A. J. Cleary, R. D. Falgout, V. E. Henson, J. E. Jones, T. A. Manteuffel, S. F. McCormick, and J. W. Ruge, Algebraic multigrid based on element interpolation (AMGe), SIAM J. Sci. Comput. (submitted), 1998.
  2. J. E. Jones and P. S. Vassilevski, AMGe based on element agglomeration, (1999) submitted.

This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.