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?
3 Answers
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.
"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.
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.
-
$\begingroup$ Bernardo, welcome to
scicomp
! Your second paragraph looks more like a question than an answer. Could you please cut it from your answer and paste it into a separate question? The question you ask in your second paragraph is a good example of the type of question we like to see atscicomp
. $\endgroup$ Feb 12, 2012 at 23:56