› Multigrid Simulator Back
Numerical Methods Simulator

Multigrid Simulator — V-cycle for 1D Poisson

Solve the 1D Poisson equation with a V-cycle multigrid method and watch the residual fall by orders of magnitude faster than Gauss-Seidel alone.

Parameters
Fine grid points N (2^k+1)
pts
Number of V-cycles
—
GS smoother sweeps (pre/post each)
—
Wave number k of sin(kπx)
—

We solve -u''(x)=f(x) with u(0)=u(1)=0, using the exact solution sin(kπx) and forcing f(x)=(kπ)²sin(kπx). N is rounded to the nearest 2^k+1.

Results
—
MG residual ‖r‖ after 5 cycles
—
GS residual at equivalent work
—
Residual ratio GS/MG (speed-up)
—
L2 error vs. exact solution
Solution u(x) and convergence history ‖r‖

Top = solution u(x) (blue solid = MG numerical solution / grey dashed = exact sin(kπx)) / Bottom = residual ‖r‖ on a log scale (blue = MG, red = GS only)

Theory & Key Formulas

A finite-difference discretisation of the 1D Poisson equation gives, on each interior point i, the symmetric tridiagonal linear system $A\mathbf{u}=\mathbf{f}$ with diagonal 2 and off-diagonals -1.

Fine grid (spacing h) discretisation:

$$-\frac{u_{i-1}-2u_i+u_{i+1}}{h^2}=f_i$$

Gauss-Seidel smoothing (removes high-frequency error):

$$u_i^{(\text{new})}=\tfrac{1}{2}\bigl(u_{i-1}^{(\text{new})}+u_{i+1}^{(\text{old})}+h^2 f_i\bigr)$$

Full-weighting restriction (fine→coarse) and linear prolongation (coarse→fine):

$$r^{2h}_i=\tfrac{1}{4}r^{h}_{2i-1}+\tfrac{1}{2}r^{h}_{2i}+\tfrac{1}{4}r^{h}_{2i+1}$$

The whole V-cycle (recursive):

$$u\leftarrow \text{Smooth}\circ \text{Prolong}\circ V_{2h}\circ \text{Restrict}\circ \text{Smooth}(u)$$

Smooth error modes look high-frequency on the coarse grid, so the smoother kills them efficiently at every level. The result is a convergence factor that is independent of grid size and around 0.1 per cycle.

What is the Multigrid Simulator

🙋
Whenever I look at a CAE solver I see "multigrid preconditioner". What is it actually doing, and how is it different from an ordinary iterative method?
🎓
Good question. Roughly speaking, a point iteration like Gauss-Seidel can only "talk to its neighbours". Information moves only one grid spacing per sweep, so smooth (low-frequency) error needs hundreds of iterations to propagate. Multigrid drops down to a coarser grid and "carries information across the domain in one go". Push the V-cycle slider in the simulator from 1 to 5 and you will see the red GS curve drift down slowly while the blue MG line falls by orders of magnitude.
🙋
Got it. What does the "GS smoother sweeps" slider change? Surely more is always better?
🎓
That is the interesting part. Adding more smoother sweeps at each level barely improves the MG convergence factor — three sweeps or ten sweeps give almost the same slope. The smoother's only job is to kill high-frequency error, and the low-frequency content is handed off to the coarse grid. In practice you use 2 or 3 sweeps because more just wastes work. Try comparing ν=1 and ν=10 in the simulator; the blue slope hardly changes.
🙋
When I set the wave number k to 1 the solution is a single sine arch. Push it higher and it gets wavy.
🎓
k controls the spatial frequency in the forcing f(x). What is important is that MG stays robust as you sweep k from 1 to 20 — that is its big selling point: it kills error at every frequency uniformly. Gauss-Seidel, in contrast, is at its worst exactly at low k=1, where convergence becomes glacial. Try k=1 in the simulator and compare the residual cards.
🙋
When I push N up to 257 the calculation still finishes in an instant and the residual still drops cleanly. Usually finer grids make things slower, don't they?
🎓
That is MG's famous "optimal complexity". An ordinary iteration needs about 4× more iterations every time you halve h, while MG's iteration count is independent of h. Each cycle costs O(N) and you only need a constant number of them, so the whole thing is O(N). That is why a problem with ten million unknowns can be solved in tens of seconds — it is the standard inside modern large-scale CAE solvers.

Frequently Asked Questions

FAS (Full Approximation Scheme) keeps the full solution rather than just the error on each coarse grid, giving a consistent way to handle nonlinear operators. It is the method of choice for the Navier-Stokes equations, RANS turbulence closures, plasticity, and phase-change heat transfer — problems where global Newton-style linearisation is hard or expensive. The coarse-grid problem is the full nonlinear operator restricted to that grid, and the correction is added directly back to the fine solution.
Geometric multigrid assumes a regular hierarchy of grids and halves the spacing at each level. AMG uses no geometry at all — it analyses the strength of connections in the matrix A and builds a pseudo-coarsening algebraically. It applies to unstructured FEM meshes, pipe networks, circuit simulators and any large sparse problem without a natural hierarchy, and ships in libraries such as Hypre BoomerAMG and Trilinos ML inside many commercial solvers.
For large structural and thermal FEM models, MG or AMG is plugged in as a preconditioner for an iterative solver like conjugate gradient or GMRES. Plain CG converges painfully slowly because the stiffness matrix is ill-conditioned, while AMG-preconditioned CG converges in a few tens of iterations. The "PCG with AMG" option in Ansys, Abaqus and COMSOL, and the GAMG solver in OpenFOAM, are typical examples.
The main variations are the W-cycle (recursing twice at each coarse level), the F-cycle (a compromise between V and W) and full multigrid (FMG, nested iteration). W-cycles trade extra coarse-grid work for better robustness on convection-dominated or strongly anisotropic problems. FMG starts on the coarsest grid and walks up, giving an initial guess close to the discretisation error for just one or two extra V-cycles' worth of work.

Real-World Applications

Large-scale CFD solvers: OpenFOAM's GAMG, ANSYS Fluent's AMG and Star-CCM+ all use multigrid as the inner solver for the pressure Poisson equation. In SIMPLE / PISO-style algorithms the pressure equation is solved once per time step and typically accounts for 60-80% of the total run time, so an O(N) solver there decides the overall performance of the simulation.

Structural preconditioning: For large linear-elastic and thermal FEM problems the stiffness matrix is symmetric positive definite and AMG-preconditioned conjugate gradient is the de facto standard. Even at the five-million-DOF range of a typical car body model, AMG-PCG converges in a few tens of iterations. Hypre, Trilinos ML and PETSc provide the AMG backends embedded in many commercial solvers.

Atmospheric and ocean simulation: Global climate and weather models reduce to elliptic pressure equations through hydrostatic and Coriolis approximations, and these have to be solved every time step. WRF for weather, MITgcm for the ocean, and many other production models use spherical-grid geometric multigrid or parallel AMG to push real-time forecasts out across thousands of HPC cores.

Computer vision and image processing: Multigrid is also central in vision and graphics: Poisson image editing (seamless blending), HDR tone mapping, stereo disparity optimisation and fluid-based CG effects all require solving huge sparse systems each frame, and multigrid's speed is what makes real-time use possible.

Common Misconceptions and Cautions

The most common misconception is to imagine that multigrid is magic and converges fast on any problem. In reality, if the smoother and the coarsening are not matched to the operator, convergence stalls. Convection-dominated problems (advection-diffusion at high Péclet number, for example) confound point Gauss-Seidel because it cannot annihilate the high-frequency error component, and the convergence factor approaches 1. Such problems need block Gauss-Seidel, line smoothers or semi-coarsening. The simulator uses the pure Poisson equation, so you always see the ideal ~0.1 convergence factor, but tuning these knobs on real problems is the heart of multigrid engineering.

Next, people often assume more smoother sweeps must be better. Sweep the smoother slider in the simulator from 1 to 10 and you will see the final MG residual barely improves. Once the smoother has wiped out high-frequency error in a couple of sweeps, the rest is wasted work because the remaining error is smooth and must be handled by the coarser level. In practice 2 or 3 pre- and post-smoothing sweeps is standard, and an MG that already converges with ν=1 is considered efficient.

Finally, do not just keep adding V-cycles when convergence is slow. A well-built MG should reach discretisation error (O(h²)) in 5 to 10 cycles. If you need more than that, something is wrong: a mismatched smoother, mishandled boundary conditions, or a mixing of rediscretisation and Galerkin coarse operators. Rather than brute-forcing with more cycles, the right diagnostic is to verify that the per-cycle reduction factor r_{n+1}/r_n stays near 0.1 - 0.2.

Related Tools

Gauss-Seidel Simulator — Iterative Solution of Linear Systems Solve a 3-variable linear system Ax=b with the Gauss-Seidel iteration and SOR relaxation fa... 1D Linear Autoencoder Simulator — Compression Equivalent to PCA 1D linear autoencoder simulator. Compress a 10-dimensional signal into K dimensions and rec... Binomial Distribution Simulator Vary the number of trials n and success probability p to visualize the probability distribu... EM Algorithm (1D GMM) Simulator The EM algorithm (1D GMM) simulator fits a two-component Gaussian mixture to data with iter... Gauss Quadrature Simulator — Convergence of Gauss-Legendre Integration The Gauss quadrature simulator visualizes the sample points and weights of Gauss-Legendre i... Central Limit Theorem Demonstrate the Central Limit Theorem by sampling from arbitrary distributions (uniform, ex...