10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR ended on a measurement it could not fix. Twenty Gauss–Seidel sweeps from zero on the -interval plate leave of the residual and of the error, and the sweeps needed to finish grow like . It also left a clue: relaxation flattened the jagged part of the error in five sweeps, then crawled over the smooth hump. 10.5 Wave Equation Numerics & the CFL Condition sorted disturbances by wavelength too. Multigrid turns that sorting into a solver: relax where relaxation is fast, hand the smooth remainder to a coarser grid where it is jagged again, and recurse down to a grid small enough to solve exactly. On that same plate, three such cycles cost about as much as Stam’s twenty sweeps and leave a residual times smaller. The pressure solve of 10.11 2D Grids, Boundary Conditions & Staggered (MAC) Grids and 11.10 The Projection Method for Incompressible Flow is why this matters.
Transcript
- Relaxation has a blind spot. Write the error as a sum of sine waves. Each sweep of Jacobi multiplies mode k by its own factor, one minus two omega sine squared of k pi over 2N. For plain Jacobi, omega equal to 1, at N equal to 32 the smoothest hump has factor 0.9952, and the zigzag at k equal to 31 has minus 0.9952. Both survive. A smooth error looks satisfied locally, so the residual stays small while the error is large. That is why the sweeps needed grow like N squared.
- The rough half is another story. Choose omega equal to two thirds. Every mode in the upper half, k at least N over 2, is then multiplied by at most one third in size per sweep: 0.3333 at k equal to 16, and minus 0.3301 at the zigzag. The smoother need not solve anything. It only has to filter. After a few sweeps the rough part is gone, and what is left is smooth, which is exactly what a grid with spacing 2h can carry.
- The coarse grid needs something to solve. We cannot see the error, but we can compute the residual, and A e equals r. Restrict the residual by full weighting: each coarse value is a weighted average of the nine fine values around it, with weights one, two, one, over sixteen. Solve the same kind of equation on the coarse grid, with a factor of 4 on the right side. Then prolong by bilinear interpolation and add. In the N equal to 4 example, the coarse equation 2e equals 4 gives e equal to 2, and the correction is 1, 2, 1.
- Put it in order: pre-smooth, compute the residual, restrict, solve, prolong, post-smooth. Here are the measured stages for N equal to 64, with two sweeps before and two after. At the start 51.15 percent of the error energy is rough. Two sweeps drop that to 0.18 percent, though the error norm only falls to 0.6106. The correction does the heavy lifting, down to 0.0671, but interpolation kinks bring the rough share back to 31.44 percent. Two post-sweeps clean it up: error 0.0327, residual 9.04 times 10 to the minus 3. Each half does what the other cannot.
- The coarse problem is the same kind of problem, so recurse. Go down through grids of 64, 32, 16, 8 and 4, smoothing and restricting on the way, solve the smallest exactly, and climb back, prolonging and smoothing. That is a V-cycle. A pass on the coarse grid touches a quarter as many nodes in 2D, so the work is a geometric series, bounded by 4 over 3 of the fine-level work. V(2,2) measures 6.56 fine sweeps per cycle at N equal to 64: work proportional to the number of unknowns. Calling the coarse level twice makes a W-cycle.
- Now the payoff. On the plate, to a residual of 10 to the minus 6, Gauss-Seidel needs 102, 350, 1166 and 3745 sweeps for N equal to 10, 20, 40 and 80. V(2,2) needs 4 cycles every time. The work creeps from 20.8 to 26.3 only because small grids have fewer levels. The asymptotic factor is between 0.045 and 0.048 per cycle. At N equal to 40, three cycles cost about as much as Stam's twenty sweeps and leave a residual 1270 times smaller.
- To recap. Relaxation damps rough error fast and stalls on smooth error. The residual equation hands the smooth part to a coarser grid, where it is rough again. A V-cycle costs work proportional to the unknowns, and the cycle count does not grow with N. Next, spectral methods. We used sine modes only as an analysis tool, but on a box a fast sine transform diagonalises the Laplacian outright, so no iteration is needed.
Why relaxation stalls
Let solve and let be our guess. The error is , one number per node, and the residual is what we can compute without knowing . Subtract from and they are tied by one line:
Each sweep of Jacobi or Gauss–Seidel multiplies the error by a fixed matrix . A shape that only rescales is an eigenvector of (1.5 Eigenvectors & Eigenvalues), and the rescaling factor is its eigenvalue. Here the eigenvectors are the sampled sine waves of the last lesson. Any error is a sum of them, the same split into modes as in 10.3 Von Neumann Stability Analysis, and each mode is multiplied by its own factor every sweep. The hump has factor at ; the checkerboard has under plain Jacobi, so even the jagged extreme survives it. Smoothness is the trouble: a node already near the average of its neighbours looks satisfied, so a sweep barely moves it and the residual, which measures only local disagreement, stays small while the error is large.
The smoothing property
Weighted Jacobi, , is Jacobi with a damping knob; is Jacobi. Work in 1D, where on nodes has eigenvectors for , with the number of half-waves ( the hump, the zigzag). The iteration matrix gives mode the factor
For :
No helps the smooth end, which stays at . Ask less: damp the upper half, . There runs from at toward at the zigzag. Setting gives , and every upper-half mode is then multiplied by at most in size per sweep: damped by at least a factor of three, the worst being at . Plain Jacobi leaves the zigzag at .
Why the upper half? A grid with spacing can carry only the modes of the fine grid; the upper half would be misread there as smoother waves. Those must die on the fine grid, and the lower half can go below. So the smoother need not be a good solver, only a good filter. Red-black Gauss–Seidel, the lab’s choice, filters better (smoothing factor in 2D, from memory; I only measure whole cycles) and stays parallel. In 2D the modes are products of sines and “upper half” means either index.
The residual equation and the coarse-grid correction
After a few sweeps the error is smooth but unknown. We do know , and is a Poisson problem of the same kind. A smooth is well represented with half the points per side, so solve it there, , at a quarter of the unknowns in 2D, then interpolate and add. The same five-point stencil serves on the coarse grid, with zero edge values since the error vanishes where the data are given. Two transfer operators, with coarse node sitting on fine node :
- Restriction by full weighting: each coarse residual is a weighted average of the nine fine residuals around it,
- Prolongation by bilinear interpolation: fine nodes that coincide with coarse nodes copy, edge midpoints average two coarse values, cell centres average four.
One scaling detail: the stencil’s right side carries a factor , so on the grid it must be times the restricted residual, . Forget the and every correction comes out a quarter size.
Worked example. Take , on three nodes, , so , and start from . Then . One coarse node () receives , scaled to ; the coarse equation gives . Interpolating gives , so and . The middle node is exact but the ends are not, because linear interpolation of a coarse solution is a kinked fine-grid function. In modes, is equal parts hump and zigzag. One weighted-Jacobi sweep at multiplies them by and (the and entries above, because is the same) and leaves : the zigzag is gone, a small smooth hump remains, and the next coarse correction will take it.
The two-grid cycle
Put the pieces in order: pre-smooth sweeps; compute ; restrict; solve the coarse problem exactly; prolong and add; post-smooth sweeps. The lab runs this with red-black Gauss–Seidel, , written V(2,2). Its stage readout, for , the source-and-sink problem and a random start:
| stage | error energy in rough modes | 2-norm of error (start ) | residual |
|---|---|---|---|
| start | |||
| after pre-sweeps | |||
| after coarse correction | |||
| after post-sweeps |
Pre-smoothing barely shrinks the error () but changes its character: rough becomes . The correction does the heavy lifting, a -fold drop, and pays with roughness from interpolation kinks, which post-smoothing cleans up. (The two equal residuals are what the lab prints; I read the maximum as set by the rough part, which the correction does not touch, but have not isolated that.)
Measured over cycles to on the homogeneous problem from a random start, the exact two-grid cycle at shrinks the residual by per cycle. It does not depend on : the smoother’s has no in it. That -independence is a theorem for the model problem (from memory, not derived); the table below measures it.
From two grids to many: V, W and F
The coarse problem is the same kind of problem, so solve it with the same method: recursion.
cycle(level, u, b):
if level is the coarsest: solve exactly, return
smooth u, nu1 times
b2 = 4 * restrict(b - A u)
e2 = cycle(level + 1, 0, b2)
u = u + prolong(e2); smooth u, nu2 times
One recursive call per level traces a V down to the coarsest grid and back. Calling twice makes the W-cycle; the F-cycle calls an F-cycle then a V-cycle on the coarse grid (the usual definitions, from memory). On the plate at with V(2,2), grids , residual :
| cycle | cycles needed | factor per cycle | work per cycle | total work |
|---|---|---|---|---|
| V | ||||
| W | ||||
| F |
Work is counted in fine-grid sweeps (smoothing sweeps and residual evaluations; transfers are free). W and F buy nothing here because V already needs four cycles; the extra visits pay off on harder problems (from memory).
What it costs
A smoothing pass on the grid touches as many nodes as on the grid, in dimensions. A V-cycle’s work is therefore a geometric series times the fine-level work:
V(2,2) does four smoothing sweeps and one residual pass per level, so about fine sweeps in 2D, and the lab measures at and at (the coarse grids are slightly smaller than a quarter). That is work proportional to the unknowns: per cycle. Now the table the course has been building toward, on the plate with residual , Gauss–Seidel in lexicographic order as in the last lesson:
| Gauss–Seidel sweeps | ||||
| V(2,2) cycles | ||||
| multigrid work, fine sweeps | ||||
| Gauss–Seidel work over multigrid work |
Four cycles at every . The work creeps up from to only because small grids have fewer levels, so a cycle there costs sweeps rather than the limit near . Per cycle the residual falls on the plate as , , , , , a ratio creeping up from toward the asymptotic factor, which the homogeneous test puts between and for to (the estimate wobbles by with the window). Two caveats: the plate has discontinuous corners and the tolerance is absolute, so these counts belong to this problem and are no guarantee; the pressure section lists what changes in practice.
Back to Stam’s budget. At three V(2,2) cycles cost fine sweeps, about his twenty, and leave a residual of and a largest error of . Twenty Gauss–Seidel sweeps leave and : multigrid is times better in residual and times in error, at the same price.
The lab
Pick a cycle and a stage to see the solution, error and residual there; play through the stages to watch the correction remove the smooth error and leave jagged scars. The lower left plots residual against work on a log axis: Gauss–Seidel’s near-flat line against multigrid’s near-vertical drop. The lower right is the 1D factor per mode; its slider also sets the weighted-Jacobi smoother. On the plate at from zero, the smoothers compare as follows (cycles to , asymptotic factor): red-black Gauss–Seidel and ; weighted Jacobi at and ; at and ; plain Jacobi, , and . The last is the point of the smoothing property: with a filter that does not filter, the coarse grid cannot rescue the cycle. Measure scaling reproduces the table above.
The pressure solve, and what the model problem hides
Everything above was Dirichlet data on a square with a vertex-centred grid. A real projection step (11.10 The Projection Method for Incompressible Flow) differs in four ways.
- Walls are Neumann. Zero normal pressure gradient makes singular with the constant vector in its kernel (1.3 Linear Systems, Kernel & Column Space), solvable only when the right side sums to zero. Multigrid still works, with the coarse levels inheriting the singularity and the coarsest solve pinning a node or removing the mean (from memory; the lab is Dirichlet only).
- The grid is cell-centred on a MAC layout (10.11 2D Grids, Boundary Conditions & Staggered (MAC) Grids). Restriction averages four cells and prolongation interpolates from cell centres: the same idea, different stencils (from memory).
- Domains are irregular and coefficients jump, as with obstacles or variable density. Geometric coarsening and simple smoothers lose their guarantees; algebraic multigrid builds the coarse levels from the matrix entries alone, with no grid at all (from memory).
- The cycle is often a preconditioner, one V-cycle per step of conjugate gradients (from memory, as 10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR said).
The exercise: a one-dimensional V-cycle
The smoothing analysis was 1D, so build the whole machine there. The smoother and residual are given; you write restriction, prolongation and the recursion. Grid sizes are .
Concept checks
Problems
Show that lies between and for and that the smoothing factor is smallest at . Then compute at and for and say which end of the upper half dominates.
Show worked solution
For the angle lies in , so runs from up toward and falls from toward . The smoothing factor is for near that range. For the first is larger and shrinks as grows; for the second is larger and grows. They meet at , , with value . At : at , and at the zigzag, so the zigzag end dominates and the factor is about .
Find the V-cycle work factor for and the W-cycle’s, where each level is visited twice per visit to the level above. For which is the W-cycle’s work , and what happens in 1D?
Show worked solution
V: a level below the finest has of the nodes and is visited once, giving . W: level is visited times, so the ratio is and the factor : in 2D , in 3D . In 1D the ratio is : every level costs the same, there are of them, and the W-cycle costs .
Take . Gauss–Seidel’s factor per sweep is (from the last lesson). One V(2,2) cycle shrinks the residual by about . How many sweeps give the same shrinkage, asymptotically, and how does that compare with one cycle’s work of about fine sweeps?
Show worked solution
sweeps. One cycle does the asymptotic work of about sweeps for the price of : a ratio near in the asymptotic regime. The table’s ratio at is , lower, because Gauss–Seidel’s measured sits below the asymptotic estimate , for the reason the last lesson gave: under an absolute tolerance the slowest mode starts with a small residual.
Key Takeaways
- Relaxation multiplies each sine mode of the error by its own factor, which is near for smooth modes. Jacobi and Gauss–Seidel therefore stall on smooth error and sweeps grow like .
- Weighted Jacobi has factor ; at every upper-half mode is damped by at least per sweep. Plain Jacobi leaves the zigzag at .
- The residual equation lets a coarse grid solve for the smooth error. Full weighting restricts, bilinear interpolation prolongs, and the coarse right side carries a factor .
- A cycle is pre-smooth, restrict, coarse solve, prolong, post-smooth. The correction leaves rough interpolation error ( of the error’s energy at ), which the post-smoothing removes.
- The V-cycle recurses; a cycle costs times its finest-level work, so .
- Measured on the plate, V(2,2) needs cycles at , against Gauss–Seidel’s , , , sweeps. The asymptotic factor is to . Three cycles at beat Stam’s twenty sweeps by in residual.
- A pressure solve adds Neumann walls, cell-centred grids and irregular domains; those extensions and algebraic multigrid are from memory, untested in the lab.
- Next in build order is 10.12 Spectral Methods & the FFT. Our analysis used sine modes only as a tool; on a box a fast transform diagonalises the Laplacian outright, and no iteration is needed (from memory). I have not computed any of that, so I claim only the idea.