Multigrid Methods
Multigrid accelerates the solution of large linear systems by removing errors on a hierarchy of coarser grids, achieving near-optimal scaling.
Why one grid is slow
Classical iterative solvers like Jacobi or Gauss-Seidel remove high-frequency (oscillatory) error components quickly but smooth, low-frequency components very slowly. On a fine grid, smooth error takes many iterations to decay, so convergence stalls. Multigrid overcomes this by recognizing that smooth error on a fine grid looks oscillatory on a coarser grid, where a smoother can eliminate it efficiently.
By combining smoothing on a hierarchy of grids, multigrid attacks every error frequency on the grid where it is most quickly reduced. For many elliptic problems this yields convergence in a number of iterations independent of problem size, and a total cost proportional to the number of unknowns.
The multigrid cycle
A V-cycle smooths the error on the fine grid, restricts the residual to a coarser grid, solves (recursively) the coarse problem, prolongs the correction back to the fine grid, and smooths again. W-cycles and full multigrid (FMG) visit coarse grids more or start from the coarsest level to build a good initial guess. Restriction and prolongation operators transfer information between levels.
Geometric and algebraic variants
Geometric multigrid builds the grid hierarchy from the mesh geometry and is efficient when a natural coarsening exists. Algebraic multigrid (AMG) constructs the hierarchy from the matrix alone, making it applicable to unstructured problems and complicated operators where geometric coarsening is unclear.
- Smoothers remove high-frequency error on each level
- Restriction and prolongation transfer between grids
- V-, W-, and full multigrid cycling strategies
- Near-optimal O(N) scaling for many elliptic systems
Multigrid, used directly or as a preconditioner for Krylov solvers, is central to fast elliptic solves such as the field solves in field codes and the pressure or potential equations in fluid and MHD models.