A numerical exploration of algebraic multigrid

Jane Cullum

MS B256, CCS-3, Los Alamos National Laboratory, Los Alamos, NM 87545, USA


Algebraic multigrid (AMG) methods for solving large systems of linear equations, Ax=b, are matrix-based analogs of geometric multigrid methods. Both types of methods are multi-level, with the method being applied recursively at each level except at the bottom level.

In this talk we focus on AMG procedures which are based upon papers of Ruge and Stüben. At each level, except the bottom level, the procedure requires the choice of the

  1. Coarse and Fine variables
  2. Prolongation and Restriction operators
  3. Coarse problem
  4. Smoother operator
The choice of each of these components places constraints upon the choice of each of the other components. Numerically, we explore the effects of different choices upon the observed convergence. We consider example problems where AMG has been shown to work well and other example problems where AMG converges slowly.