Geometric Multigrid
A multilevel method that uses a hierarchy of nested meshes to solve elliptic problems with work proportional to the number of unknowns.
The complementary roles of smoothing and coarse correction
Simple iterative relaxations such as Gauss-Seidel are excellent at damping high-frequency (oscillatory) error components but painfully slow on smooth, low-frequency error. Geometric multigrid exploits the fact that error which is smooth on a fine mesh looks oscillatory on a coarser mesh, where relaxation can attack it efficiently. Recursing this idea across a full hierarchy of meshes yields a solver whose cost grows only linearly with problem size.
The building blocks
- A smoother (Jacobi, Gauss-Seidel, or a Krylov step) to reduce high-frequency error
- A restriction operator to transfer residuals from fine to coarse meshes
- A prolongation (interpolation) operator to transfer corrections back
- A coarse-grid operator, either rediscretized or formed by the Galerkin product
The V-cycle
A V-cycle smooths on the finest mesh, restricts the residual to the next coarser mesh, and repeats down to the coarsest mesh where the problem is solved directly. It then prolongs corrections back up, smoothing at each level. A W-cycle visits coarse levels more often for harder problems, and full multigrid nests V-cycles to reach solution accuracy in a single sweep from coarse to fine.
Strengths and limits
On structured meshes with elliptic operators, geometric multigrid is often the fastest available solver, reaching discretization accuracy in a handful of cycles. Its weakness is that it needs an explicit mesh hierarchy and mesh-aware transfer operators, which are awkward on unstructured or adaptively refined meshes. There algebraic multigrid takes over, building the hierarchy from the matrix alone. Both approaches underpin the fast field and potential solves used in large-scale plasma simulation.