the multigrid method
Every discretized elliptic PDE — a finite-element or finite-difference Laplacian — leaves you with a huge sparse linear system to solve, often millions of unknowns. Classical iterative solvers like Gauss–Seidel have an exasperating flaw: they crush the high-frequency, jagged part of the error in a few sweeps, but the smooth, large-scale part of the error barely moves, so convergence crawls to a halt. Multigrid is the elegant cure, and it is one of the few algorithms that solves such systems in time proportional to the number of unknowns — optimal complexity, the best you could hope for.
The key insight is that 'smooth on a fine grid' looks 'rough on a coarse grid'. Smooth error that a fine-grid smoother cannot touch becomes high-frequency, and therefore easy to kill, once you view it on a grid with twice the spacing. So multigrid plays the error on a hierarchy of grids. The V-cycle does this: apply a few smoothing sweeps on the fine grid (kill the high-frequency error there), compute the leftover residual, RESTRICT it down to a coarser grid (average it onto fewer points), solve the smaller problem for the smooth error there — recursively, going coarser and coarser until the grid is tiny and solvable directly — then PROLONG (interpolate) that correction back up and add it to the fine-grid solution, finishing with a few more smoothing sweeps to clean up interpolation error. Each frequency band of the error gets handled on the grid where it is easiest to remove.
The payoff is dramatic: a well-tuned multigrid solver converges to a fixed accuracy in a number of cycles that does NOT grow as the grid is refined, giving O(N) total work — whereas a single-grid iterative method needs more and more iterations as N grows, and a direct sparse solve scales worse. It is the gold-standard solver for elliptic problems and the inner engine of many large simulations. The caveats are real: classical (geometric) multigrid needs a hierarchy of nested grids and works best for nice elliptic operators; for unstructured meshes, jumping coefficients, or non-elliptic problems it can degrade, which is why algebraic multigrid (AMG) — which builds the coarse levels from the matrix alone, no grid required — and multigrid-as-a-preconditioner were developed.
Solving the 2D Poisson equation on a million-point grid: Gauss–Seidel alone needs roughly a million sweeps and is hopeless. A multigrid V-cycle reaches the same accuracy in about a dozen cycles, and crucially that dozen does NOT grow when you refine to four million points — the per-unknown cost is essentially constant.
Handle each error frequency on the grid where it is easiest to remove.
Multigrid's O(N) optimality is not automatic — it depends on the smoother and the coarse operator matching the problem. For strongly anisotropic or jumping-coefficient operators, naive multigrid can stall, and you need tailored smoothers or algebraic multigrid.