How to construct a prolongation and restriction operator for an algebraic multigrid solver?

Question

I am trying to solve a linear system of equations that is sparse, but lacks any kind of banded structure. I have heard that there is a way to extend the principles of a multigrid solver for implicit finite difference schemes to a general linear problem (if I'm not mistaken, it's called algebraic multigrid solver). After reading some literature on it, I am still very confused on how to interpolate (i.e. prolong and restrict) between coarse and fine grids without exploiting the nice structure of the banded matrices like those from a finite difference scheme. Is there some heuristic to it? Can anyone give an example?

Answer 1

First, if you have a structured grid, you might want to use geometric instead of algebraic multigrid due to some theoretical and efficiency advantages (e.g. ability to rediscretize instead of using Galerkin coarse grid operators). Algebraic multigrid methods generally fall in two categories.

Classical Algebraic Multigrid

This method was introduced by Brandt, McCormick, and Ruge in 1982 and has strong theory for $M$-matrices. Brandt (1986) has the standard convergence theory. See BoomerAMG from the Hypre package for a popular and highly scalable parallel implementation. A more robust and general variant is called Bootstrap AMG, see this recent paper from Brandt, Brannick, Kahl, and Livshits.

Smoothed Aggregation

Smoothed aggregation from Vaněk, Mandel, and Brezina (1996) is a more recent method that has proven to be useful for vector problems like elasticity. The general approach is to start with vectors characterizing the near-null space of the operator (e.g. rigid body modes in elasticity), construct aggregates using connectivity of the matrix (usually by finding a maximal independent set of $A^T A$), and "smooth" the aggregates (using the operator) to create lower energy coarse basis functions. Popular parallel implementations are ML from Trilinos, Prometheus from Mark Adams (2004 Gordon Bell prize), PCGAMG in PETSc (also from Mark Adams, mostly a complete replacement for Prometheus), and the smoothed aggregation component of the CUDA-based GPU code CUSP.

Note that all software mentioned above can be accessed through a common interface using PETSc.

Answer 2

"Multigrid" by Trottenberg, et al, is an excellent book and it looks like most of it is available on Google books. It has an appendix on AMG and you will probably need to get some background in MG from the rest of the book. "A Multigrid tutorial" is also a good book.

Answer 3

I would suggest chapter 8 of "A Multigrid Tutorial" (2Ed) by W. L. Briggs, V. E. Henson and S. F. McCormick. It gives a general idea on some important concepts like algebraic smoothness and strong dependence. It also explain how to define the interpolation operator (coarse-grid operator too) and how to select coarse grid.