Algebraic Multigrid
Algebraic multigrid builds a coarse-grid hierarchy from the matrix entries alone, extending multigrid to unstructured and irregular problems.
Multigrid without a mesh
Geometric multigrid needs a sequence of nested grids, which is natural on structured meshes but awkward on unstructured ones. Algebraic multigrid (AMG) removes that requirement: it constructs the coarse levels, the interpolation operators, and the coarse-grid operators using only the entries of the fine-grid matrix. This makes it a near black-box solver for symmetric positive-definite systems arising from many discretizations.
AMG infers which unknowns are strongly connected by examining the size of off-diagonal matrix entries relative to the diagonal. Strongly connected unknowns should be represented well on coarser levels, guiding the coarsening.
Setup and solve phases
AMG has a setup phase that analyzes the matrix, selects coarse variables, builds interpolation, and forms coarse operators by the Galerkin triple product; and a solve phase that runs standard multigrid cycles using these operators. Setup cost is nontrivial and is amortized when the same matrix is solved for many right-hand sides.
Variants and robustness
Classical Ruge-Stueben AMG selects coarse points from the fine grid; smoothed-aggregation AMG groups unknowns into aggregates and smooths the resulting basis. Both perform well on scalar elliptic problems; systems of PDEs and strongly anisotropic or convective operators require specialized strengthening to remain robust.
- Coarsening driven by matrix strength of connection
- Galerkin triple product forms coarse operators
- Ruge-Stueben (points) vs smoothed aggregation (aggregates)
- Setup cost amortized over repeated solves
AMG is a common preconditioner for the large sparse systems that appear in implicit fusion transport and MHD solvers on complex unstructured meshes, where a geometric hierarchy is not readily available.