Is multigrid the same as grid search?

No. Grid search explores parameter choices; multigrid solves numerical equations using a hierarchy of representations.

Must a physical mesh be supplied?

Not always. Algebraic multigrid constructs its levels using information from the linear system.

Does one coarse correction always solve the problem?

No. The worked example is exact only for an error captured by its chosen coarse space.

AI Glossary / Mathematics and optimization / Intermediate

Multigrid method

Definition

A multigrid method solves a numerical problem by combining calculations at several levels of resolution. For a linear system, it alternates local relaxation with corrections obtained from smaller, coarser problems. The levels work together to reduce different components of the error, often making large discretized problems much faster to solve than repeated fine-level relaxation alone.

What it means

Many simulation and image-processing tasks lead to large sparse systems Ax=b. A simple iteration may quickly remove error that changes sharply between neighboring grid points while making slow progress on error that varies smoothly over many points. Such smooth error can often be represented with fewer unknowns.
Multigrid uses that smaller representation to compute a correction, then transfers the correction back to the detailed problem. The aim remains solving the original fine-level equations. It is not simply replacing the requested detailed answer with a cheaper low-resolution answer. Algebraic multigrid builds a hierarchy from matrix structure rather than requiring an explicit geometric grid.

How it works

Start with an approximate fine-grid solution x. Apply a few suitable relaxation steps, called pre-smoothing. Compute the residual r=b−Ax, which measures how far the current approximation fails to satisfy the equations. Restrict that residual to a coarse level and approximately solve a coarse error equation.
Prolong the coarse correction back to the fine level and add it to x. Post-smoothing can reduce error introduced or left by the transfer. Repeat recursively through a hierarchy: a V-cycle descends to coarser levels and returns toward finer ones. A common coarse operator is A_c=RAP, where R restricts and P prolongs. The smoother, transfers, and coarse operators must work well together.

Three practical examples

A physical simulation can use multigrid when solving suitable discretized diffusion or Poisson equations on a large mesh.
An image-processing application can solve certain spatial reconstruction equations using corrections at multiple resolutions.
A scientific machine-learning workflow can use a multigrid solver or preconditioner inside the numerical simulations that generate its training data.

Think of it this way

Think of correcting a drawing by alternating between close inspection and a smaller overview. Close inspection reveals local irregularities, while the overview makes broad distortions easier to see. The analogy is limited: multigrid transfers precisely defined residuals and corrections, rather than relying on visual judgment or merely shrinking an image.

Worked example

Consider an original three-unknown linear system. Let A have rows (2,−1,0), (−1,2,−1), and (0,−1,2). Choose b=(0,2,0) and initial approximation x=(0,0,0). The exact solution is (1,2,1), since direct multiplication gives b.
Use one coarse unknown and prolongation P=(1/2,1,1/2) as a column. Choose restriction R=(1/4,1/2,1/4), so R is half of P transposed. Multiplying gives AP=(0,1,0), and therefore the coarse operator A_c=RAP=1/2. The fine residual is b, and its restriction is r_c=Rb=1.
Solve the one-number coarse equation (1/2)e_c=1, giving e_c=2. Prolongation produces Pe_c=(1,2,1). Adding this correction to the initial approximation solves the fine system exactly.
That exactness is special: the entire initial error lies in the one-dimensional range of P. To see the limitation, change the exact solution to (1,0,−1), with right-hand side (2,0,−2), again starting at zero. Restriction now gives Rb=0. The coarse correction is zero even though the fine error is nonzero. A relaxation step or a richer hierarchy is needed to address the error that this coarse representation cannot see.
The calculation isolates coarse-grid correction; it is not a complete practical V-cycle with smoothing. It also distinguishes residual from error: they are related by Ae=r when e is the exact solution minus the current approximation, but they are generally different vectors.

Illustrative case study

In a fictional example, Stonebridge Imaging develops a reconstruction tool that solves a sparse spatial equation for each image. Its first implementation applies many relaxation sweeps and eventually makes slow progress. Engineers introduce a coarse correction and measure convergence on representative image sizes.
They discover that the transfer rule and boundary treatment matter as much as the number of levels. The team retains residual checks against the original fine equations and compares total setup-plus-solve time. This invented case illustrates an evaluation process, without claiming a particular speedup or reconstruction-quality gain.

Common misconceptions and mistakes

Multigrid is not guaranteed to be fast for every matrix. Strong directional coupling, unsuitable relaxation, difficult coefficients, or a poor coarse space can impair convergence. A hierarchy that works on one problem family may need adaptation for another.
The residual is not the solution error itself. Its interpretation depends on the operator and scaling. Moreover, reducing algebraic error does not eliminate modeling or discretization error.
Do not promise linear total cost solely because multiple levels are present. Near-linear performance requires suitable convergence and bounded work across the hierarchy, including setup when that cost matters. Parallel communication and coarse-level work can also limit practical speed.

Business use

Multigrid matters commercially when repeated numerical solves dominate simulation, design, or image-processing costs. A useful evaluation records the problem family, setup time, solve time, memory use, convergence tolerance, and behavior as resolution increases.
It can also serve as a preconditioner within another iterative solver, rather than acting as a standalone solver. For an AI project using simulation outputs, maintain the same numerical accuracy requirements when comparing methods. A faster calculation that stops at a looser tolerance is not an equivalent comparison, and solver accuracy alone does not validate the underlying physical model.

Check your understanding

A coarse correction is zero. Does that prove the fine solution is exact?

Answer: No. The restricted residual may be zero while the fine residual is nonzero, as the second right-hand side in the worked example demonstrates.

Related terms

Iterative method
Residual
Preconditioning
V-cycle
relaxation
algebraic multigrid
restriction
prolongation
coarse-grid correction

Learn next

Multiply the matrices in the worked example by hand and verify both residuals. Then add one weighted Jacobi step to the second case and inspect which error remains. Study why an effective smoother and an effective coarse space must complement one another.

Sources

Primary teaching source: Gilbert Strang, Multigrid Methods, section 6.3 of original course notes: https://math.mit.edu/classes/18.086/2006/am63.pdf . Grid-transfer and coarse-operator constructions were consulted. The three-unknown examples and fictional application above are original illustrations.

Previous: Multifidelity simulation Next: Multilabel indicator matrix