the multigrid method

Multigrid is the closest thing numerical analysis has to a miracle: for the discretized elliptic PDEs it targets, it solves systems with n unknowns in O(n) work — optimal, meaning the cost is merely proportional to the size of the answer, which no other method achieves for these problems. It grew from a sharp observation about why simple iterations like Gauss-Seidel are slow. Such iterations are local: each update mixes only neighbouring unknowns. They are therefore very good at smoothing out the jagged, high-frequency part of the error (neighbours quickly agree), but hopeless at the smooth, long-wavelength part of the error (information has to crawl across the whole grid one neighbour at a time).

Here is the key insight that unlocks everything. A smooth error on a fine grid, when viewed on a COARSER grid (with half as many points per dimension), looks comparatively jagged — its wavelength is now only a few coarse grid-spacings. So the smooth error that a fine-grid smoother cannot touch becomes a high-frequency error that a coarse-grid smoother CAN kill. Multigrid exploits this recursively. The V-cycle goes: do a few smoothing sweeps on the fine grid to remove the jagged error; compute the residual and transfer it down to a coarser grid (restriction); recursively solve the residual equation there (where its now-rough components get smoothed, and even smoother components get passed down further still); transfer the correction back up (prolongation) and add it; finish with a few more smoothing sweeps. Every frequency of error meets a grid on which it looks rough and is therefore quickly annihilated.

The payoff is spectacular: a fixed, small number of V-cycles — independent of grid size — drives the error below tolerance, giving genuinely O(n) total cost where Gauss-Seidel needs O(n^2) and even preconditioned CG needs more. Multigrid is the gold standard for Poisson-like and other elliptic problems and is often used as a preconditioner for Krylov methods on harder ones. Its honest limits: classical geometric multigrid needs a grid hierarchy and is most natural for smooth elliptic operators; it struggles on highly anisotropic, strongly convective, or irregular problems without careful tuning. Algebraic multigrid (AMG) builds the coarse levels from the matrix alone, extending the idea to unstructured problems at extra setup cost.