10.4 Implicit Methods & Crank–Nicolson ended on a loose end. In 2D the implicit time step needs a matrix with five nonzeros per row, not three, and the Thomas algorithm no longer applies. Stam faces the same matrix twice per frame, for diffusion and for pressure, and solves it by sweeping the grid about twenty times. 9.6 Laplace's Equation: Rectangles & Disks already ran such sweeps on a plate: for Jacobi, for Gauss–Seidel, for SOR, at residual on intervals. This lesson is the theory and practice behind those numbers: where they come from, why they grow with refinement, and what a solver that stops after twenty sweeps returns.
Transcript
- At every interior node the five-point stencil gives one equation: four times the centre value minus its four neighbours equals h squared times the source. Stack the unknowns and this is A u equals b, with 4 on the diagonal and minus 1 at four neighbours. For N equal 40 that is 1521 unknowns and only 7449 nonzeros. The inverse is dense, so nobody forms it. An iteration touches only the stencil. The question is how many.
- Write A as D minus L minus U. Evaluate the right side at the old iterate and you have Jacobi. Use each new value the moment it exists and you have Gauss-Seidel. Either way the error is multiplied by a matrix each sweep, so what matters is its spectral radius. For Jacobi that is cosine of pi h, which is 0.99692 at N equal 40, and 2309 sweeps. For Gauss-Seidel it is the square, 0.99384, and 1166 sweeps, about half. Jacobi also multiplies the checkerboard error by nearly minus 1.
- Colour the nodes like a checkerboard. Every neighbour of a red node is black, so all the red nodes can be updated at once, and then all the black ones from the fresh reds. A lexicographic sweep is a recurrence. This is two fully parallel passes, which is why GPU solvers use it. Is it as fast? It keeps the factor cosine squared of pi h, 0.9938 at N equal 40. The counts differ, 1166 and 1268, but that is a difference in the start, not the end.
- Successive over-relaxation goes past the neighbour average by a factor omega between 1 and 2. Young's result, which the lab confirms, gives the best omega as 2 over 1 plus sine of pi h, and a factor of omega minus 1. The gap shrinks like h, not h squared. At N equal 40 the optimum is 1.8545, factor 0.8545. The curve drops steeply to the optimum and rises only slowly after it, so when unsure, overshoot. The minimum is flat, 95 sweeps at 1.85, 96 at the optimum.
- Now race them. Each solver starts from the same plate and runs to residual 10 to the minus 6. Jacobi takes 2309 sweeps, Gauss-Seidel 1166, red-black 1268. SOR at 1.85 takes 95, and conjugate gradients 84. The lab also measures the factor and compares it with the prediction. Jacobi and Gauss-Seidel match to four digits. SOR's measurement is low because 95 sweeps is a short run for a method with a transient.
- Now vary N. The number of sweeps against N, on log axes. SOR and conjugate gradients sit near slope 1. The Jacobi family sits at 1.75, not 2, so the counts rise by 3.5, 3.4 and 3.2 per doubling, not 4. The reason is in the logarithm: the rate itself falls by 4.09, 4.01 and 4.00 per doubling, exactly the one over h squared law, but with an absolute tolerance the number of decades to cover shrinks as the grid refines.
- Why do twenty sweeps not suffice? A sweep replaces a node by its neighbours' average. A node that sticks out is corrected at once, while a node near the average barely moves. So rough error dies fast and smooth error slowly. The residual is A times the error, small exactly for smooth error: a small residual is not a small error. Start from noise, with 49.4 percent of the error energy rough. After 20 sweeps Gauss-Seidel has smoothed it. Jacobi keeps a checkerboard tail, 2.2 percent, and SOR at 1.85 keeps 47.1 percent. It does not smooth at all.
- Relaxation uses only the current iterate. Conjugate gradients uses all the earlier ones. Each step is one product with A, a few dot products, and no omega to tune. The result worth knowing is the energy-norm bound, with the factor square root kappa minus 1 over square root kappa plus 1. That is about 1 minus pi h, so about 1 over h iterations. At N equal 40 the bound is 0.92439 and the measured contraction is 0.81644. Read the gap as pessimism, not contradiction. It needs 84 iterations, against SOR's 96.
- Stam's solver does a fixed 20 Gauss-Seidel sweeps, with no tolerance. From zero on our N equal 40 plate, they leave a residual of 6.67 times 10 to the minus 3, which is 2.67 percent of the start, and about 6670 times our tolerance. The largest error has fallen only from 0.9496 to 0.573, so 60 percent of the error remains. Twenty sweeps remove the rough, local part and hardly touch the smooth part. Incompressibility is restored locally, but not the large-scale pressure.
- To recap: Jacobi 2309 sweeps, Gauss-Seidel 1166, SOR 95, conjugate gradients 84. Sweeps grow like 1 over h squared for the Jacobi family, and like 1 over h for optimal SOR and CG. The catch is smooth error, which survives. Twenty sweeps leave 2.67 percent of the residual. The fix is multigrid, lesson 10.9, which is not yet written: relax with Gauss-Seidel, then correct the smooth remainder on a coarser grid. Before that, the staggered grid lesson builds the stencils whose product is this Laplacian.
The system behind the stencil
At every interior node of the five-point stencil says , with known edge values moved to the right side. Stack the unknowns into and this is : on the diagonal, at four neighbours, nothing else. For that is unknowns and a matrix with entries, of them nonzero. At there are unknowns; a dense matrix needs about terabytes, the five numbers per row need megabytes.
So nobody forms . It is dense (a source at one node moves every node, the Green’s function of 9.6 Laplace's Equation: Rectangles & Disks), and banded elimination costs about in 2D (from memory). An iteration touches only the stencil, about five operations per unknown: many cheap approximate solves instead of one expensive exact one. The question is how many.
The eigenvectors of are the sampled sines , with the eigenvalues of 10.1 Finite Differences: Discretizing Derivatives:
At the smallest is (the smooth hump), the largest (the checkerboard), and the condition number is .
Stopping rule. The residual is the largest change one Jacobi sweep would still make, . We stop below , absolute: the Laplace lesson’s definition, so shared numbers agree. Unless stated, the problem is that plate (top edge , others , interior starting at zero).
Splitting: Jacobi and Gauss–Seidel
Write with the diagonal () and , the negated strictly lower and upper parts. Then reads . Evaluate the right side at the old iterate:
That is Jacobi. Gauss–Seidel uses each new value the moment it exists: a node’s west and south neighbours are already new, so and . Subtracting the exact solution from either update gives , so . The error shrinks from every start exactly when the spectral radius is below , and in the long run by per sweep; a factor takes about sweeps.
For Jacobi the eigenvalues are free: shares ‘s eigenvectors and has eigenvalues . The largest is at , the smallest at the checkerboard:
At , and , the factor by which Jacobi’s residual under-reports its error. Note the second statement: Jacobi multiplies the most oscillatory error by nearly and almost never removes it. For Gauss–Seidel the standard result (Young, lexicographic order; from memory) is : about half the sweeps. Red-black ordering gives a proof.
Red-black ordering
Colour the nodes like a checkerboard, red where is even. Every neighbour of a red node is black and vice versa, so all red nodes can be updated at once (none reads another red node), then all black nodes from the fresh reds. A lexicographic sweep is a recurrence; a red-black sweep is two fully parallel passes, which is why GPU solvers use it.
Is it as fast? In red-black order the Jacobi matrix is , with averaging black neighbours into red nodes and the reverse. A red-black sweep sets , then . The square of the block matrix is , so the eigenvalues of are the squares of Jacobi’s: . At both orderings contract by per sweep (measured below), though the counts differ, lexicographic and red-black: a difference in the start, not the end.
SOR and the optimal factor
Successive over-relaxation goes further than the neighbour average: with ( is Gauss–Seidel). Young’s result for the model problem (from memory; the lab tests it) is that with the SOR eigenvalues satisfy . The roots merge at the best , and beyond it become a complex pair of modulus :
The gap shrinks like , not . At , and . Sweeps to residual on the plate:
| predicted factor | sweeps | |
|---|---|---|
| (Gauss–Seidel) | ||
| (optimal) | ||
The curve drops steeply to the optimum and rises only linearly after it, so when unsure, overshoot. The minimum is flat ( at , which is just below the optimum and on the formula’s root branch, against at it). At the optimum, exceeds the asymptotic estimate , because near it the iteration is nearly defective and has a long transient: SOR’s residual at sweep is , above its start. The formula needs a square with Dirichlet data; on odd domains the best is unknown, one reason to want CG.
The lab: five solvers on one problem
Each solver runs from the same start to residual . The readout gives iterations to tolerance, the predicted factor, and the measured factor, the geometric mean of the residual ratio over the last half of the run. At on the plate: Jacobi (predicted , measured ), Gauss–Seidel (, ), red-black (, ), SOR at (, ), CG (bound , measured ). SOR’s measurement is low because sweeps is a short run for a method with a transient: to residual it reads .
Counting: against
The button measure scaling runs on the plate, SOR at its own , and prints the slope of log count against log :
| solver | slope | ||||
|---|---|---|---|---|---|
| Jacobi | |||||
| Gauss–Seidel | |||||
| red-black GS | |||||
| SOR, | |||||
| CG |
SOR and CG sit near slope . The Jacobi family sits at , not , with per-doubling ratios , , . The count is with , and , the slowest mode’s initial residual, is times its error and so falls like : with an absolute tolerance drops by per doubling. The rate itself is clean: Jacobi’s measured gap is , , , , falling by , , per doubling, and Gauss–Seidel’s is about twice that ( to ). Counts follow the law of the rate up to a logarithm.
Error against residual, and the seed of multigrid
Mode of the error is multiplied each sweep by its own eigenvalue of . The mechanism is local: the update replaces a node by its neighbours’ average, so a node that sticks out (rough error) is corrected at once, while a node already near the average (smooth error) barely moves. The change a sweep makes, the residual, is , small exactly for smooth . A small residual is not a small error.
The lab’s random start shows it. Take the source-and-sink problem at with noise in the interior. The error energy in rough sine modes ( or above ) starts at :
| after | Jacobi | Gauss–Seidel | red-black | SOR at | CG |
|---|---|---|---|---|---|
| iterations | below | below | |||
| iterations | below | below | below |
Gauss–Seidel flattens the rough part in five sweeps. Jacobi keeps a tail ( at sweep ) of near-checkerboard modes with factor near , so its residual is at sweep against Gauss–Seidel’s (start ). SOR at does not smooth at all: fast on smooth modes, nearly blind to rough ones. What remains is the lowest hump: the cosine between the error and rises for Gauss–Seidel from to at sweep and at sweep .
Conjugate gradients
Relaxation uses only the current iterate; conjugate gradients (CG) uses all earlier ones. For a symmetric positive definite , with and direction :
A step is one product (a stencil pass like a sweep), a few dot products, and no . The directions make each step the best over everything tried so far. The result worth knowing (from memory, not derived) is the energy-norm bound
Jacobi’s factor is , CG’s . Here , so and the factor is about : about iterations with nothing to tune. At the bound factor is and the measured residual contraction ; the bound is a worst case for another norm, and a run to measures , so read the gap as pessimism, not contradiction. The counts: iterations against SOR’s at its optimal , slope . CG needs only a symmetric positive definite matrix, and with a multigrid preconditioner (from memory) it is a production pressure solver.
Stam’s lin_solve
Stam’s routine does a fixed Gauss–Seidel sweeps, no tolerance: . For diffusion (11.11 Stam's Stable Fluids, Step by Step) , , and Jacobi’s factor is , below by at any grid size, so sweeps are plenty for small (Problem 2). For pressure, , : our Poisson problem with the slow factor and a start of . Twenty Gauss–Seidel sweeps from zero on our plate leave:
- a residual of , of the start () and about times our tolerance;
- a largest error of against at the start: of the error remains.
This is the -sweep picture of 11.10 The Projection Method for Incompressible Flow, where the cylinder’s influence had barely spread. The mechanism is the table above: sweeps remove the rough, local part of the residual (divergence one cell can see) and hardly touch the smooth part, so incompressibility is restored locally while the large-scale pressure that steers the stream around the body is not built. Games accept it because the viewer sees swirls, not mass budgets; the price, measured in 11.11 Stam's Stable Fluids, Step by Step, is that finer grids kept less vorticity.
Worked example: three radii on a grid
For (, nine unknowns) the formulas give , , and . The playground builds the matrix and finds the three spectral radii numerically.
The exercise
Implement Jacobi and Gauss–Seidel on the plate and measure what the theory predicts.
The counts for are (Jacobi) and (Gauss–Seidel). They grow by , per doubling in both cases, while the rate ratios are , (Jacobi) and , (Gauss–Seidel): the approach to is in the rate.
Concept checks
Problems
The 1D problem with interior nodes () has . Find , , , , and the sweeps to cut the error by for each.
Show worked solution
has eigenvalues : , , . So , , , . Sweeps : , , , about , , .
For , show that Jacobi has . For , , find the reduction from Jacobi sweeps, and the largest for which Gauss–Seidel sweeps reach .
Show worked solution
, and the neighbour average has largest eigenvalue magnitude . At : , and . Gauss–Seidel gives , so , , , .
For , estimate the sweeps to reduce the slowest error by for Jacobi and for optimal SOR.
Show worked solution
, so Jacobi needs sweeps. , , : about sweeps, times fewer. At about operations a sweep that is against .
Key Takeaways
- The five-point Poisson problem is a sparse system: unknowns and nonzeros at . We iterate because the inverse is dense.
- gives . Jacobi’s follows from the Laplacian eigenvalues; Gauss–Seidel’s and SOR’s are from memory, and the lab confirms them.
- Red-black ordering makes each half-sweep parallel and keeps .
- On the plate at , residual : Jacobi , Gauss–Seidel , red-black , SOR at , CG . The rate quarters per doubling of ; counts show slope for the Jacobi family and about for SOR and CG.
- Relaxation kills rough error fast and smooth error slowly, and a small residual is not a small error. Jacobi leaves checkerboard error and SOR leaves all rough error; Gauss–Seidel smooths.
- CG needs about iterations with no parameter.
- Twenty Gauss–Seidel sweeps from zero leave of the residual and of the error on the plate: a local fix, not the global solution.
- Next: 10.11 2D Grids, Boundary Conditions & Staggered (MAC) Grids builds the divergence and gradient stencils whose product is this Laplacian, with its wall rows; the multigrid lesson (10.9 Multigrid) attacks the smooth error.