Algebraic Multigrid
A multilevel solver that builds its coarse problems purely from the matrix entries, needing no knowledge of the underlying geometry.
Multigrid without a grid
Multigrid methods accelerate the solution of large sparse systems by combining relaxation (which kills high-frequency error) with correction on coarser problems (which kills low-frequency error that relaxation cannot touch). Geometric multigrid derives its coarse levels from a mesh hierarchy. Algebraic multigrid (AMG) instead constructs the hierarchy from the matrix alone, making it applicable to unstructured meshes, irregular discretizations, and matrices with no obvious geometry.
The setup phase
AMG runs in two phases. The setup phase analyzes the matrix graph to select a subset of unknowns as the coarse level, based on the notion of strong connections (large off-diagonal entries relative to the row). It then builds interpolation (prolongation) operators that transfer corrections from coarse to fine, and forms the coarse matrix by the Galerkin triple product P^T A P.
The solve phase
The solve phase applies a V-cycle or W-cycle: relax on the fine level, restrict the residual, recurse to solve the coarse correction, prolong it back, and relax again. Because the coarse problems are much smaller, the total work per cycle is proportional to the number of unknowns, giving near-optimal scaling.
- Strength-of-connection threshold controls coarsening aggressiveness
- Classical (Ruge-Stuben) vs smoothed-aggregation are the two main variants
- Works as a standalone solver or as a preconditioner for CG or GMRES
When AMG shines
AMG is the go-to for elliptic and diffusion-dominated problems on unstructured meshes: pressure Poisson solves, electrostatic potentials, and the elliptic pieces of MHD equilibrium. It struggles on strongly nonsymmetric or highly anisotropic operators unless specialized coarsening is used. In those cases it is often paired as a preconditioner rather than a standalone solver, contributing robustness where a single-level method would stall.