multigrid

Multigrid is a family of numerical methods for solving large linear systems, especially those arising from discretizing elliptic partial differential equations. The central idea is to accelerate convergence by operating on a hierarchy of grids or levels that capture solution error at different spatial scales. Smoothers such as Gauss-Seidel or Jacobi reduce high-frequency errors on a fine grid, while a coarse-grid correction handles low-frequency errors by transferring the residual to a coarser grid where it can be solved or approximated more cheaply. The computed correction is then interpolated back to finer grids.

A typical multigrid cycle consists of pre-smoothing, restricting the residual to a coarser grid, solving or approximately solving the coarse-grid system, prolongating the correction to the finer grid, and post-smoothing. On the coarsest level the system is solved directly or approximately. Common cycle types include the V-cycle, W-cycle, and full multigrid FMG, which builds the solution across levels.

There are two main families: geometric multigrid GMG, which uses a sequence of grids inherited from the discretization, and algebraic multigrid AMG, which constructs the grid hierarchy from the system matrix and is well suited to unstructured meshes and general discretizations. Multigrid methods are often combined with other iterative solvers, such as conjugate gradient or GMRES, as preconditioners.

Applications include Poisson and diffusion problems, elasticity, and various fluid dynamics discretizations. When properly designed, geometric multigrid methods achieve optimal or near-linear computational complexity in the number of unknowns, though performance depends on problem features like anisotropy and boundary conditions.