Multigrid Methods

Multigrid solves elliptic systems in near-linear time by damping errors across a hierarchy of grids, each scale handling the errors it resolves best.

Errors have scales

Simple iterations like Gauss-Seidel quickly smooth high-frequency error but barely touch smooth, low-frequency error, which is why they stall. Multigrid exploits this: it removes high-frequency error on a fine grid, then transfers the remaining smooth error to a coarser grid where it looks high-frequency and is again cheap to remove.

The V-cycle

• Smooth: apply a few relaxation sweeps on the current grid to damp high-frequency error.
• Restrict: transfer the residual to a coarser grid.
• Recurse: solve the coarse-grid correction, directly at the coarsest level.
• Prolong: interpolate the correction back and smooth again.

Near-optimal complexity

Because each error scale is handled on the grid where it is cheapest to eliminate, multigrid can solve elliptic problems in O(n) work, with an iteration count that is nearly independent of grid size. This optimal scaling is what makes it the fastest solver known for many large elliptic PDEs.

Geometric and algebraic

Geometric multigrid builds the coarse grids from the mesh geometry and is ideal for structured problems. Algebraic multigrid (AMG) constructs the hierarchy from the matrix entries alone, requiring no mesh, which makes it a powerful black-box preconditioner for unstructured and complex problems. Both are commonly used to precondition Krylov solvers.

# multigrid as a preconditioner (schematic)
# from pyamg import smoothed_aggregation_solver
# ml = smoothed_aggregation_solver(A)
# x = ml.solve(b, tol=1e-10)

Multigrid, standalone or as a Krylov preconditioner, is a leading choice for the large elliptic field solves in breeder Hyperion simulations because its cost grows almost linearly with resolution.