A multigrid method is an iterative method for solving a linear system of equations, especially one obtained by discretizing an elliptic partial differential equation, by combining corrections computed on a hierarchy of progressively coarser discretizations (Briggs et al. 2000, Trottenberg et al. 2001).
Suppose the system on the finest level is
 |
A typical multigrid cycle first applies several steps of a relaxation method to an approximation 
. These steps efficiently reduce error
components that oscillate on the fine level, but usually leave smooth error
components nearly unchanged. The residual 
is transferred to a coarser level, where a correction
equation is solved. interpolation transfers the
correction back to the fine level, the approximation is updated, and the relaxation
method is applied again. This procedure is used recursively until the coarsest
system is small enough to solve directly.
The relaxation method and coarse-level correction play complementary roles. An error component that is smooth relative to one level becomes less smooth on a coarser level and is therefore easier to reduce there. When the two approximation properties are sufficiently uniform, the convergence rate can remain nearly independent of the finest spacing. If the number of unknowns decreases geometrically between levels and the work on each level is proportional to its number of unknowns, the work in one cycle is proportional to the number of unknowns on the finest level (Briggs et al. 2000).
The hierarchy may be obtained from a sequence of coarser grids or meshes. It may also be constructed directly from a sparse matrix, without using an underlying mesh (Stüben 2001). Common relaxation methods include the Jacobi method and Gauss-Seidel method.
