Flow Lab

Syllabus / Module 10: Numerical Methods for PDEs

Lesson 10.9

Multigrid

Why Jacobi kills high frequencies but not low ones; coarse-grid correction; V-cycles; near-optimal O(N) Poisson solves.

Written byClaude Sonnet

🌊
Why this matters for simulation: Production fluid solvers use multigrid or multigrid-preconditioned CG for pressure.

By the end of this lesson you can…

  • Explain, with the error written as a sum of sine modes, why Jacobi and Gauss–Seidel stall: smooth modes have factors near $1$.
  • Derive the weighted-Jacobi factor $g_k = 1 - 2\omega\sin^2(k\pi/2N)$ and show that $\omega = 2/3$ damps every mode in the upper half of the spectrum by at least a factor of $3$.
  • Write the residual equation $A\mathbf e = \mathbf r$ and build a coarse-grid correction from full-weighting restriction and linear prolongation.
  • Assemble a two-grid cycle and a V-cycle, and say how the W-cycle and F-cycle differ.
  • Show that a V-cycle costs about $1/(1-2^{-d})$ fine-grid passes per fine-level pass, and read a table in which the cycle count stays flat while Gauss–Seidel's grows like $N^2$.
  • Say what a pressure solve adds to the model problem: Neumann walls, cell-centred grids and irregular domains.
On this page
·
  1. Why relaxation stalls
  2. The smoothing property
  3. The residual equation and the coarse-grid correction
  4. The two-grid cycle
  5. From two grids to many: V, W and F
  6. What it costs
  7. The lab
  8. The pressure solve, and what the model problem hides
  9. The exercise: a one-dimensional V-cycle
  10. Concept checks
  11. Problems
  12. Key Takeaways

10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR ended on a measurement it could not fix. Twenty Gauss–Seidel sweeps from zero on the 4040-interval plate leave 2.67%2.67\% of the residual and 60%60\% of the error, and the sweeps needed to finish grow like N2N^2. 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 12701270 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.

▶ Video A smooth error survives relaxation; weighted Jacobi damps the rough half; the residual equation on a coarse grid; restriction and prolongation; the two-grid cycle, the V-cycle, and the costcaptions only
Transcript
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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 u∗\mathbf u^* solve Au=bA\mathbf u = \mathbf b and let u\mathbf u be our guess. The error is e=u∗−u\mathbf e = \mathbf u^* - \mathbf u, one number per node, and the residual r=b−Au\mathbf r = \mathbf b - A\mathbf u is what we can compute without knowing u∗\mathbf u^*. Subtract AuA\mathbf u from Au∗=bA\mathbf u^* = \mathbf b and they are tied by one line:

Ae=r.A\mathbf e = \mathbf r .

Each sweep of Jacobi or Gauss–Seidel multiplies the error by a fixed matrix BB. A shape that BB only rescales is an eigenvector of BB (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 cos⁡πh=0.99692\cos\pi h = 0.99692 at N=40N = 40; the checkerboard has −0.99692-0.99692 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, u←u+ω(neighbour average−u)\mathbf u \leftarrow \mathbf u + \omega(\text{neighbour average} - \mathbf u), is Jacobi with a damping knob; ω=1\omega = 1 is Jacobi. Work in 1D, where A=tridiag⁡(−1,2,−1)A = \operatorname{tridiag}(-1, 2, -1) on N−1N-1 nodes has eigenvectors sin⁡(jkπ/N)\sin(jk\pi/N) for k=1,…,N−1k = 1, \dots, N-1, with kk the number of half-waves (k=1k = 1 the hump, k=N−1k = N-1 the zigzag). The iteration matrix I−ω2AI - \tfrac{\omega}{2}A gives mode kk the factor

gk=1−2ωsin⁡2kπ2N.g_k = 1 - 2\omega\sin^2\frac{k\pi}{2N} .

For N=32N = 32:

kk1188161624243131
ω=1\omega = 10.99520.99520.70710.707100−0.7071-0.7071−0.9952-0.9952
ω=2/3\omega = 2/30.99680.99680.80470.80470.33330.3333−0.1381-0.1381−0.3301-0.3301

No ω\omega helps the smooth end, which stays at 1−O(h2)1 - O(h^2). Ask less: damp the upper half, k≥N/2k \ge N/2. There gkg_k runs from 1−ω1 - \omega at k=N/2k = N/2 toward 1−2ω1 - 2\omega at the zigzag. Setting 1−ω=−(1−2ω)1 - \omega = -(1 - 2\omega) gives ω=2/3\omega = 2/3, and every upper-half mode is then multiplied by at most 1/31/3 in size per sweep: damped by at least a factor of three, the worst being 0.33330.3333 at k=16k = 16. Plain Jacobi leaves the zigzag at 0.99520.9952.

Why the upper half? A grid with spacing 2h2h can carry only the modes k<N/2k \lt N/2 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 1/41/4 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 r\mathbf r, and Ae=rA\mathbf e = \mathbf r is a Poisson problem of the same kind. A smooth e\mathbf e is well represented with half the points per side, so solve it there, A2he2h=r2hA_{2h}\mathbf e_{2h} = \mathbf r_{2h}, 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 (I,J)(I, J) sitting on fine node (2I,2J)(2I, 2J):

  • Restriction by full weighting: each coarse residual is a weighted average of the nine fine residuals around it,
r2h=116(121242121)rh.\mathbf r_{2h} = \frac{1}{16}\begin{pmatrix}1&2&1\\2&4&2\\1&2&1\end{pmatrix}\mathbf r_h .
  • 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 h2h^2, so on the 2h2h grid it must be 44 times the restricted residual, b2h=4r2h\mathbf b_{2h} = 4\mathbf r_{2h}. Forget the 44 and every correction comes out a quarter size.

Worked example. Take N=4N = 4, A=tridiag⁡(−1,2,−1)A = \operatorname{tridiag}(-1, 2, -1) on three nodes, b=(1,1,1)\mathbf b = (1, 1, 1), so u∗=(1.5,2,1.5)\mathbf u^* = (1.5, 2, 1.5), and start from u=0\mathbf u = \mathbf 0. Then r=b\mathbf r = \mathbf b. One coarse node (N=2N = 2) receives 14(1+2+1)=1\tfrac14(1 + 2 + 1) = 1, scaled to b2h=4\mathbf b_{2h} = 4; the coarse equation 2e=42e = 4 gives e2h=2e_{2h} = 2. Interpolating gives (1,2,1)(1, 2, 1), so u=(1,2,1)\mathbf u = (1, 2, 1) and e=(0.5,0,0.5)\mathbf e = (0.5, 0, 0.5). 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, e\mathbf e is equal parts hump and zigzag. One weighted-Jacobi sweep at ω=2/3\omega = 2/3 multiplies them by 0.80470.8047 and −0.1381-0.1381 (the k=8k = 8 and k=24k = 24 entries above, because k/Nk/N is the same) and leaves e=(16,13,16)\mathbf e = (\tfrac16, \tfrac13, \tfrac16): 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 ν1\nu_1 sweeps; compute r\mathbf r; restrict; solve the coarse problem exactly; prolong and add; post-smooth ν2\nu_2 sweeps. The lab runs this with red-black Gauss–Seidel, ν1=ν2=2\nu_1 = \nu_2 = 2, written V(2,2). Its stage readout, for N=64N = 64, the source-and-sink problem and a random start:

stageerror energy in rough modes2-norm of error (start =1= 1)residual
start51.15%51.15\%111.781.78
after 22 pre-sweeps0.18%0.18\%0.61060.61060.1750.175
after coarse correction31.44%31.44\%0.06710.06710.1750.175
after 22 post-sweeps0.15%0.15\%0.03270.03279.04×10−39.04\times10^{-3}

Pre-smoothing barely shrinks the error (0.610.61) but changes its character: 51%51\% rough becomes 0.18%0.18\%. The correction does the heavy lifting, a 99-fold drop, and pays with 31%31\% 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 33 to 1010 on the homogeneous problem from a random start, the exact two-grid cycle at N=64N = 64 shrinks the residual by 0.03730.0373 per cycle. It does not depend on NN: the smoother’s 1/31/3 has no hh in it. That hh-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 N=64N = 64 with V(2,2), grids 64/32/16/8/464/32/16/8/4, residual 10−610^{-6}:

cyclecycles neededfactor per cyclework per cycletotal work
V440.04540.04546.566.5626.226.2
W440.03730.03739.099.0936.336.3
F440.03730.03738.538.5334.134.1

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 2h2h grid touches 1/2d1/2^d as many nodes as on the hh grid, in dd dimensions. A V-cycle’s work is therefore a geometric series times the fine-level work:

1+2−d+2−2d+⋯  <  11−2−d=2, 43, 87(d=1,2,3).1 + 2^{-d} + 2^{-2d} + \cdots \;\lt\; \frac{1}{1 - 2^{-d}} = 2,\ \tfrac43,\ \tfrac87 \quad (d = 1, 2, 3).

V(2,2) does four smoothing sweeps and one residual pass per level, so about 5×43=6.75 \times \tfrac43 = 6.7 fine sweeps in 2D, and the lab measures 6.566.56 at N=64N = 64 and 6.616.61 at N=128N = 128 (the coarse grids are slightly smaller than a quarter). That is work proportional to the unknowns: O(Nd)O(N^d) per cycle. Now the table the course has been building toward, on the plate with residual 10−610^{-6}, Gauss–Seidel in lexicographic order as in the last lesson:

NN1010202040408080
Gauss–Seidel sweeps1021023503501166116637453745
V(2,2) cycles44444444
multigrid work, fine sweeps20.820.824.724.725.925.926.326.3
Gauss–Seidel work over multigrid work4.94.914144545142142

Four cycles at every NN. The work creeps up from 20.820.8 to 26.326.3 only because small grids have fewer levels, so a cycle there costs 5.25.2 sweeps rather than the limit near 6.66.6. Per cycle the residual falls on the N=40N = 40 plate as 0.250.25, 5.06×10−35.06\times10^{-3}, 1.47×10−41.47\times10^{-4}, 5.24×10−65.24\times10^{-6}, 2.17×10−72.17\times10^{-7}, a ratio creeping up from 0.0200.020 toward the asymptotic factor, which the homogeneous test puts between 0.0450.045 and 0.0480.048 for N=16N = 16 to 128128 (the estimate wobbles by ±0.002\pm0.002 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 N=40N = 40 three V(2,2) cycles cost 19.419.4 fine sweeps, about his twenty, and leave a residual of 5.24×10−65.24\times10^{-6} and a largest error of 6.94×10−56.94\times10^{-5}. Twenty Gauss–Seidel sweeps leave 6.67×10−36.67\times10^{-3} and 0.5730.573: multigrid is 12701270 times better in residual and 83008300 times in error, at the same price.

The lab

◆ Interactive Run a multigrid cycle stage by stage, watch the error change character, and compare its residual against Gauss-Seidel's

Loading simulation…

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 ω\omega slider also sets the weighted-Jacobi smoother. On the plate at N=64N = 64 from zero, the smoothers compare as follows (cycles to 10−610^{-6}, asymptotic factor): red-black Gauss–Seidel 44 and 0.04540.0454; weighted Jacobi at ω=0.8\omega = 0.8 77 and 0.13460.1346; at ω=2/3\omega = 2/3 88 and 0.18860.1886; plain Jacobi, ω=1\omega = 1, 3636 and 0.88020.8802. 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 AA 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 n=2m−1n = 2^m - 1.

🐍 PythonThe weighted-Jacobi factor per mode, and three sweeps on a mixed error
⌘/Ctrl + Enter
🧪 Coding exerciseExercise: restriction, prolongation and a recursive V-cycle
⌘/Ctrl + Enter

Concept checks

✅ Concept check

Why does multigrid send the residual equation to a coarser grid only after relaxing?

✅ Concept check

With $\omega = 2/3$ the factor of mode $k = N/2$ is $1 - \omega$. What number is it?

✅ Concept check

In 3D the V-cycle's work, as a multiple of the finest-level work, tends to $1/(1 - 2^{-3})$. What is that, as a decimal?

✅ Concept check

On the $N = 64$ plate the plain-Jacobi ($\omega = 1$) smoother needs $36$ cycles where red-black Gauss–Seidel needs $4$. Why?

✅ Concept checkselect all that apply

Select all that are true of the transfer operators in this lesson.

Problems

✏️ Pen & paperThe best damping factor●○○

Show that gk=1−2ωsin⁡2(kπ/2N)g_k = 1 - 2\omega\sin^2(k\pi/2N) lies between 1−ω1 - \omega and 1−2ω1 - 2\omega for k≥N/2k \ge N/2 and that the smoothing factor is smallest at ω=2/3\omega = 2/3. Then compute gg at k=N/2k = N/2 and k=N−1k = N-1 for ω=4/5\omega = 4/5 and say which end of the upper half dominates.

Show worked solution

For N/2≤k≤N−1N/2 \le k \le N-1 the angle kπ/2Nk\pi/2N lies in [π/4,π/2)[\pi/4, \pi/2), so sin⁡2\sin^2 runs from 12\tfrac12 up toward 11 and gkg_k falls from 1−ω1 - \omega toward 1−2ω1 - 2\omega. The smoothing factor is max⁡(∣1−ω∣,∣1−2ω∣)\max(\lvert 1 - \omega\rvert, \lvert 1 - 2\omega\rvert) for ω\omega near that range. For ω<2/3\omega \lt 2/3 the first is larger and shrinks as ω\omega grows; for ω>2/3\omega \gt 2/3 the second is larger and grows. They meet at 1−ω=2ω−11 - \omega = 2\omega - 1, ω=2/3\omega = 2/3, with value 1/31/3. At ω=4/5\omega = 4/5: g=0.2g = 0.2 at k=N/2k = N/2, and →−0.6\to -0.6 at the zigzag, so the zigzag end dominates and the factor is about 0.60.6.

✏️ Pen & paperWork in $d$ dimensions●●○

Find the V-cycle work factor 1/(1−2−d)1/(1 - 2^{-d}) for d=1,2,3d = 1, 2, 3 and the W-cycle’s, where each level is visited twice per visit to the level above. For which dd is the W-cycle’s work O(Nd)O(N^d), and what happens in 1D?

Show worked solution

V: a level ℓ\ell below the finest has 2−dℓ2^{-d\ell} of the nodes and is visited once, giving 1/(1−2−d)=2,43,871/(1 - 2^{-d}) = 2, \tfrac43, \tfrac87. W: level ℓ\ell is visited 2ℓ2^{\ell} times, so the ratio is 2/2d2/2^d and the factor 1/(1−21−d)1/(1 - 2^{1-d}): in 2D 1/(1−12)=21/(1 - \tfrac12) = 2, in 3D 1/(1−14)=431/(1 - \tfrac14) = \tfrac43. In 1D the ratio is 11: every level costs the same, there are log⁡2N\log_2 N of them, and the W-cycle costs O(Nlog⁡N)O(N\log N).

✏️ Pen & paperHow many Gauss–Seidel sweeps is one cycle worth?●●○

Take N=80N = 80. Gauss–Seidel’s factor per sweep is cos⁡2(π/80)=0.998459\cos^2(\pi/80) = 0.998459 (from the last lesson). One V(2,2) cycle shrinks the residual by about 0.0470.047. How many sweeps give the same shrinkage, asymptotically, and how does that compare with one cycle’s work of about 6.66.6 fine sweeps?

Show worked solution

ln⁡(1/0.047)/ln⁡(1/0.998459)=3.058/0.0015425≈1980\ln(1/0.047)/\ln(1/0.998459) = 3.058/0.0015425 \approx 1980 sweeps. One cycle does the asymptotic work of about 20002000 sweeps for the price of 6.66.6: a ratio near 300300 in the asymptotic regime. The table’s ratio at N=80N = 80 is 142142, lower, because Gauss–Seidel’s measured 37453745 sits below the asymptotic estimate ln⁡(0.25/10−6)/0.0015425≈8060\ln(0.25/10^{-6})/0.0015425 \approx 8060, 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 11 for smooth modes. Jacobi and Gauss–Seidel therefore stall on smooth error and sweeps grow like N2N^2.
  • Weighted Jacobi has factor 1−2ωsin⁡2(kπ/2N)1 - 2\omega\sin^2(k\pi/2N); at ω=2/3\omega = 2/3 every upper-half mode is damped by at least 33 per sweep. Plain Jacobi leaves the zigzag at 0.99520.9952.
  • The residual equation Ae=rA\mathbf e = \mathbf r lets a coarse grid solve for the smooth error. Full weighting restricts, bilinear interpolation prolongs, and the coarse right side carries a factor 44.
  • A cycle is pre-smooth, restrict, coarse solve, prolong, post-smooth. The correction leaves rough interpolation error (31%31\% of the error’s energy at N=64N = 64), which the post-smoothing removes.
  • The V-cycle recurses; a cycle costs 1/(1−2−d)1/(1 - 2^{-d}) times its finest-level work, so O(Nd)O(N^d).
  • Measured on the plate, V(2,2) needs 44 cycles at N=10,20,40,80N = 10, 20, 40, 80, against Gauss–Seidel’s 102102, 350350, 11661166, 37453745 sweeps. The asymptotic factor is 0.0450.045 to 0.0480.048. Three cycles at N=40N = 40 beat Stam’s twenty sweeps by 12701270 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.
Finished this lesson?

Mark it complete to track your progress (saved in this browser). Reading every section does this for you.