Multigrid: the V-cycle over pluggable smoothers and grids
How MTL5’s multigrid driver works, and why it is built as a recursion over four pluggable roles — a grid hierarchy, inter-grid transfer operators, a smoother, and a coarse solver. Multigrid is the method that turns the slow tail of a stationary iteration into an O(n) solve, and the design mirrors the composability of the Krylov solvers: the driver owns only the cycle; every numerical ingredient is supplied.
The subsystem is the multigrid driver plus the grid-transfer operators in
itl/mg/
(namespace mtl::itl::mg).
The idea: split the error by frequency across grids
Section titled “The idea: split the error by frequency across grids”A smoother damps the high-frequency (oscillatory) components of the error in a few sweeps, but barely touches the low-frequency (smooth) components — which is why a stationary iteration stalls. Multigrid’s insight is that smooth error on a fine grid looks oscillatory on a coarser grid, where a smoother can damp it cheaply. So it recursively pushes the residual down to coarser grids, smooths at each, and interpolates the correction back up:
smooth (kill high freq) → restrict residual to coarser grid → [solve the coarse problem the same way, recursively] → prolongate the correction back → smooth againEach grid handles the frequency band it damps efficiently, and the coarsest grid — small enough to solve exactly — mops up what remains. The result is a solver whose cost is O(n) for the model problems it targets, instead of the O(n^1.5) or worse of a lone smoother or unpreconditioned Krylov method on a PDE.
Decision 1 — the V-cycle (and W-cycle) recursion
Section titled “Decision 1 — the V-cycle (and W-cycle) recursion”The core is vcycle(x, b, level), a direct transcription of the idea:
void vcycle(vector_type& x, const vector_type& b, int level) { if (level == coarsest) { coarse_solve_(x, b); return; } // base case: solve exactly
for (int s = 0; s < nu_pre_; ++s) smoothers_[level](x, b); // pre-smooth r = b - A[level] * x; // residual r_coarse = restrict(R[level], r); // fine -> coarse e_coarse = 0; vcycle(e_coarse, r_coarse, level + 1); // recurse (solve A_c e_c = r_c) x += prolongate(P[level], e_coarse); // coarse -> fine, correct for (int s = 0; s < nu_post_; ++s) smoothers_[level](x, b); // post-smooth}Pre-smooth, restrict the residual, recurse on the coarse-grid error equation (starting from zero), prolongate the correction, post-smooth. The recursion bottoms out at the coarsest level with a direct solve. The W-cycle is the same body with the recursion invoked twice per level — more coarse-grid work per visit, more robust for harder problems. V and W are one recursion shape with a one-line difference, so they are the two methods and nothing else.
Decision 2 — composition over four pluggable roles
Section titled “Decision 2 — composition over four pluggable roles”The multigrid object is assembled from independent ingredients, exactly the
composition pattern the Krylov solvers
use:
multigrid(levels, // A[0] (finest) … A[L-1] (coarsest) — the grid hierarchy restrictors, // R[0] … R[L-2] — fine→coarse transfer matrices prolongators, // P[0] … P[L-2] — coarse→fine transfer matrices smoother_factory, // makes a smoother for a given level's matrix coarse_solver, // solves the coarsest level exactly nu_pre, nu_post); // smoothing countsThe driver knows the cycle; it does not know which smoother or coarse solver you
use. Any itl::smoother (Jacobi, Gauss-Seidel, SOR)
plugs in through the factory, and any callable that solves the coarse system plugs in
as coarse_solver. That is what ties this subsystem to the smoother one: multigrid
is the composition layer, the smoothers are the components. Swap the smoother, the
cycle count, or the hierarchy depth without touching the driver.
Decision 3 — inter-grid transfer is a sparse matvec
Section titled “Decision 3 — inter-grid transfer is a sparse matvec”Restriction and prolongation are not special machinery — they are
compressed2D matrices,
and applying them is an ordinary sparse matrix-vector product:
r_coarse = R · r_fine R : n_coarse × n_fine (fine → coarse)e_fine = P · e_coarse P : n_fine × n_coarse (coarse → fine)For the shipped 1-D geometric case, make_restriction_1d builds R with the
standard full-weighting stencil [¼, ½, ¼], and make_prolongation_1d builds
P by linear interpolation — related by the classic P = 2·Rᵀ. Both are
assembled with the compressed2D inserter and applied
with a hand CRS matvec. Casting grid transfer as “just” SpMV with purpose-built
sparse operators means the entire sparse-matrix and matvec toolchain is reused; the
multigrid driver adds no new linear-algebra primitive, only the cycle that sequences
them.
Decision 4 — type erasure for the per-level smoother collection
Section titled “Decision 4 — type erasure for the per-level smoother collection”One implementation choice stands out against MTL5’s usual compile-time-generic
style. The per-level smoothers are stored as a homogeneous vector of
std::function:
std::vector<std::function<void(vector_type&, const vector_type&)>> smoothers_;std::function<void(vector_type&, const vector_type&)> coarse_solve_;The constructor builds one smoother per level via the factory and type-erases it
into a std::function. This is a runtime-dispatch cost the rest of the library
avoids — and it is the right call here, because the hierarchy holds a
collection of smoothers, one per level, that must live in a single container and
be indexed by level at run time. A std::vector needs a single element type;
std::function provides it while still letting each level’s smoother be any callable
the factory produced. The erasure is confined to the driver’s storage; the smoothers
themselves stay statically typed.
Decision 5 — multigrid is both a solver and a Krylov preconditioner
Section titled “Decision 5 — multigrid is both a solver and a Krylov preconditioner”The driver exposes two faces:
- A standalone iteration.
operator()(x, b)applies one V-cycle; repeated application is a convergent solver in its own right. - A preconditioner.
solve(x, b)/adjoint_solve(x, b)apply one V-cycle asM⁻¹, satisfying thePreconditionerconcept. This is the powerful combination — multigrid-preconditioned CG — where one V-cycle per Krylov step gives grid-independent convergence.
That second face closes a loop across the whole itl/ subsystem: multigrid is built
from smoothers (which, symmetric, are themselves Krylov preconditioners), and
multigrid is itself a Krylov preconditioner. The same small parts compose at every
level. (adjoint_solve equals solve, valid when the cycle is symmetric — symmetric
smoothers with matching pre/post counts; and solve const_casts to run the
mutating cycle through the const preconditioner interface — a small, honest wart of
that adaptation.)
What the design deliberately does not do
Section titled “What the design deliberately does not do”- Geometric, 1-D transfer operators only.
make_restriction_1d/make_prolongation_1dbuild the 1-D full-weighting / linear-interpolation operators. There is no algebraic multigrid (AMG), whereR/Pare derived fromA’s graph, and no built-in 2-D/3-D geometric transfers — though the driver itself is dimension-agnostic given the matrices, so a caller can supply their own. - The coarsest solve is exact and external. The base case delegates to the
supplied
coarse_solver; the driver does not prescribe how the small coarse system is solved. - Reference-grade, not a tuned MG library. Like the Krylov eigensolvers, this is a legible reference implementation — the cycle and the composition are the point, not a production AMG with aggressive coarsening and smoother tuning.
Where it sits in the stack
Section titled “Where it sits in the stack”containers (compressed2D level matrices + R/P transfer operators; dense_vector state) │smoothers (itl/smoother: the per-level high-frequency error damper) │▶ MULTIGRID (itl/mg: the V/W-cycle that sequences smooth → restrict → recurse → prolongate → smooth, over a supplied hierarchy) │(optionally) Krylov solver (itl/krylov: preconditioned by one V-cycle)Multigrid adds no arithmetic primitive of its own. It is pure orchestration: it sequences smoother sweeps, sparse matvecs (the transfers), and a coarse solve into a recursion whose whole is far more than its parts — an O(n) solver, or a grid-independent preconditioner, assembled from pieces documented elsewhere.
File map
Section titled “File map”| File | Role |
|---|---|
itl/mg/multigrid.hpp | the V-cycle / W-cycle driver; solver operator() and Preconditioner solve |
itl/mg/restriction.hpp | make_restriction_1d (full-weighting) + restrict (SpMV) |
itl/mg/prolongation.hpp | make_prolongation_1d (linear interp, P = 2·Rᵀ) + prolongate |
itl/smoother/ | the smoothers the driver applies per level |
For the smoothers it sequences, see the smoothers architecture; for the Krylov methods it can precondition, the iterative solvers doc; for the CRS matrices and inserter it builds transfers with, the compressed2D doc.