10.6 Advection Schemes: Upwind, Lax–Wendroff & Beyond ended with every scheme tied to a Courant number of at most one: the stencil only looks a cell or two away. 11.11 Stam's Stable Fluids, Step by Step ran Stam’s advection at a Courant number of and nothing broke, and 9.10 First-Order PDEs: Advection & Characteristics gave the one-dimensional reason: walk back along the characteristic and read the value there. This lesson takes that sketch to the plane and prices each choice: the backtrace, the interpolation, the sharpness lost, and what the method breaks. By the end Stam’s advect() is five lines, and you know what each of them spends.
Transcript
- The new value at a cell is the old value at its foot, the place the arriving parcel stood one step earlier. Euler finds the foot with the velocity at the node. The midpoint rule, RK2, uses the velocity halfway back.
- In a rotation the Euler foot is perpendicular to the radius, so it lies outside the circle, farther out by the square root of 1 plus theta squared. Each step reads the picture at a larger radius, so the dye creeps inward. With 60 steps per revolution the radius factor is 0.7209 for Euler and 0.9991 for RK2. On the bump alone the centroid error is 6.713 cells with Euler, 0.275 with RK2.
- Both dyes after one revolution at CFL 5.03. The exact answer is the start. RK2 is nearly in the right place. Euler has crept inward: the centroid is off by 3.938 cells, against 0.162 for RK2, and 48.03 percent of the mass has gone.
- The foot falls between cell centres, and bilinear blends the four neighbours with these weights. All are at least zero and they sum to 1, so the new value is an average and cannot leave the range of the old ones. That is the maximum principle, at any Courant number: in the lab, bilinear dye stays between 0 and 1 from CFL 0.5 to 20. The cost is a variance each step.
- That variance is numerical diffusion. Take both dyes on the 96 by 96 grid, one revolution at CFL 1, which is 302 steps, bilinear with RK2. The centroid is right and mass is kept, but the square's peak falls to 0.6663 and the L 2 error is 0.1357. On the bump alone the peak falls to 0.2264, within 4 percent of the prediction.
- Bigger steps smear less in total, because there are fewer interpolations. The L 2 error falls from 0.1357 at CFL 1 to 0.0827 at 5 and 0.0750 at 10. Then the foot error takes over, and CFL 20 gives 0.1363.
- Mass is not conserved. The Euler backtrace has Jacobian determinant 1 plus theta squared, so it samples more area each step. At CFL 1 the lab drifts minus 12.16 percent, against a predicted factor of 0.8775. At CFL 5.03 it drifts minus 48.03 percent, against 0.5198. RK2 at CFL 1 keeps plus 0.04 percent.
- To stop the smearing, use more cells. Catmull-Rom cubic interpolation at one half has weights minus a sixteenth, nine sixteenths, nine sixteenths, and minus a sixteenth. Its spread is zero, so it adds no smoothing. But two weights are negative: Godunov again. On the bump the L 2 error drops from 0.05261 to 0.005550.
- On the square the negative weights show. Bilinear's L 2 error is 0.1251. Unclamped cubic halves it to 0.06142, but overshoots to 1.216 and dips to minus 0.1782. Clamp to the four nearest values and the range is restored, with L 2 error 0.0662 and mass 1.88 percent above the start, because clipping undershoots adds mass.
- Error correction. Advect forward, then back, and half the difference from the start estimates one step's damage. MacCormack adds it to the forward result; BFECC advects the corrected field. Unclamped, BFECC reaches L 2 error 0.06294, but with max 1.192 and min minus 0.1589. Clamped, it is 0.06769, with mass 2.03 percent high. At CFL 1 that is no better than clamped cubic.
- In a compressing flow mass is lost by design. The spiral flow adds an inward drift, so the divergence is minus 1. The step solves D q D t equals zero: q keeps its values while the area shrinks. After one revolution the lab reads 0.3676 of the mass, against e to the minus 1, which is 0.3679. If q is a density, 63 percent has vanished, and you need a conservative form.
- Stam's advect is five lines. Lines one and two are the Euler backtrace, clipped inside the grid. Then the four neighbours, the weights, and the blend. Run in a solid rotation at CFL 1, that Euler choice pays minus 12.16 percent mass and 0.868 cells of centroid error. Switch to RK2 and it is plus 0.04 percent and 0.013 cells.
- Your exercise. A Gaussian on a 48 by 48 grid, one revolution in 48 steps. RK2 gives L 2 error 0.0378 and keeps the mass. Euler gives 0.0969 and a mass ratio of 0.445, against about 0.442 predicted. With RK2, more steps smear more: 24 steps give 0.0272, and 96 give 0.0640.
- To recap: backtrace, then interpolate. Bilinear is bounded but smears, cubic sharpens until it overshoots, and mass is only approximately kept. Stam's step also diffuses, and an explicit step needs r at most one half. Next, implicit methods and Crank-Nicolson, lesson 10.4: backward Euler is stable at any step, and the system is tridiagonal.
The backtrace in 2D
The new value at a cell centre is the old value at the foot of its characteristic, the place the arriving parcel stood one step earlier:
These are the Euler and midpoint steps of 4.3 Runge–Kutta Methods & Butcher Tableaux, run with step . The test flow is solid-body rotation about the centre of a unit box, , , . After exactly one revolution (time ) the exact answer is the starting picture, so every difference belongs to the method.
Let and let be the position relative to the centre. The Euler foot is , where turns a vector by . The vectors and are perpendicular and equally long, so
The foot lies outside the circle through the node, so each step reads the picture at a larger radius and the dye appears at a smaller one: the pattern spirals inward. After steps the radius is multiplied by and the angle lags by . The midpoint foot is , with length : the radius error is fourth order in , and the angle leads by about per step.
The lab grid has cells and quotes the Courant number at radius : . At (60 steps per revolution, ) the formulas give, per revolution:
| backtrace | radius factor | angle error |
|---|---|---|
| Euler | lag | |
| RK2 | lead |
At the node from the centre the Euler foot misses the exact one by cells per step, the RK2 foot (the lab’s foot function against the exact foot) by . Run the smooth bump alone (dye: smooth bump only, bilinear) for one revolution at CFL : the centroid error reads cells with Euler and with RK2. The inward creep predicted for the bump (radius ) is cells. It is the classic Euler spiral of 4.2 The Euler Family: Forward, Backward, Heun & Midpoint: interpolation cannot fix it, the second velocity evaluation does.
Reading between cells: bilinear weights
The foot falls between cell centres. Let its fractional position inside the cell be , each in . Bilinear interpolation blends the four surrounding values with weights
All four are at least and they sum to . A weighted average with non-negative weights cannot leave the range of what it averages, so however far the foot sits. That is the maximum principle (10.3 Von Neumann Stability Analysis writes it as ) and the whole stability proof. In the lab, bilinear dye never leaves at any CFL from to .
What it costs. The weights have a spread. In the variance is cells squared, in it is , and since the weights are products, and are uncorrelated. Each step adds that variance to the picture, as a diffusion step does. A Gaussian of variance per axis loses peak height like in 2D.
The lab’s bump has per axis. At CFL ( steps) it sits at radius and moves cells per step, in a direction that turns once around, so the offset is cells and the mean of over the circle is . Per axis that adds , so and the peak falls to of its starting height ( as sampled, so ). The lab (bilinear, RK2, bump only, one revolution) reads max , within . Summing along the bump’s path at CFL (a short script) predicts ; the lab reads .
Bigger steps smear less in total: fewer interpolations. With the full pattern (bilinear, RK2) the error after one revolution is at CFL , at and at ; then the foot error takes over, and CFL gives .
Cubic interpolation: sharper, and not bounded
To stop smearing, use more than four cells. Catmull-Rom cubic interpolation in one direction uses cells at offsets from the foot’s lower neighbour, with weights (fraction )
and a 2D value is the tensor product, sixteen cells. At the weights are . First, their spread about the foot is : quadratics are reproduced, so the smoothing bilinear adds is gone. Second, two weights are negative. That is Godunov’s theorem from 10.6 Advection Schemes: Upwind, Lax–Wendroff & Beyond again: a linear rule that does better than straight lines needs a negative weight, and a negative weight can overshoot.
The lab shows both (one revolution, CFL , RK2). Smooth bump alone: bilinear error , cubic , minimum only . Sharp square alone: cubic reaches max , min , against and for bilinear, with error against .
A clamp restores the bounds: clip the result to the minimum and maximum of the four nearest cell values. On the square: max , min , , mass above the start. The scheme is now nonlinear, as in 10.6 Advection Schemes: Upwind, Lax–Wendroff & Beyond. The clip raises undershoots, which adds mass, and cuts overshoots, which removes it; here the net is a gain.
Error correction: MacCormack and BFECC
Smoothing happens going back as well as forward, so a round trip measures it. Let be one advection step. Compute
where is advection by the reversed flow. If were exact, . Each pass smooths, so is about twice one step’s damage. Two ways to use the estimate:
- MacCormack (from memory): . Two advections, correction added at the end.
- BFECC (back and forth error compensation and correction, from memory): advect the corrected field, . Three advections.
Both are second order on smooth data (from memory), and neither is monotone. The limiter is the clamp above: clip to the range of the four old values around the foot.
At CFL , bilinear, RK2, square alone (the lab’s numbers, 302 steps): plain bilinear has and max . BFECC unclamped reaches with max and min . With the clamp, max , min and , and the mass is above the start. Clamped cubic, one advection with sixteen reads, gave and : at this setting limited BFECC is no better, so its extra two advections buy a different trade, not a free one.
With the full pattern MacCormack is cheaper and worse: clamped against for clamped BFECC, and mass against . At CFL neither helps: clamped BFECC reads against for plain bilinear. The estimate needs one step’s error to be small, and at fifteen steps per revolution it is not.
Mass is not conserved
The weights for each new value sum to one. The weights each old value receives, summed over the new values that read from it, need not. If the foot map spreads cells apart, dye in unread cells disappears. The Euler backtrace has Jacobian determinant and samples a larger area each step, so mass is multiplied by per revolution. With the full pattern and bilinear interpolation:
| setting | mass drift after one revolution |
|---|---|
| Euler, CFL 1 (302 steps) | (predicted factor ) |
| Euler, CFL 5.03 (60 steps) | (predicted factor ) |
| RK2, CFL 1 | |
| RK2, CFL 20 (15 steps) |
Rotation is divergence-free, so the exact mass is constant and every drift above is the scheme’s. Now compress. The lab’s spiral flow adds the inward drift , , so . Semi-Lagrangian advection solves : keeps its values while the area it covers shrinks as . After one revolution (bilinear, RK2, CFL ) the lab reads mass of the start, against for that equation. If is a density, the right equation keeps the mass and of it has vanished. A compressing flow needs a conservative form: the finite-volume lesson (10.10).
Stam’s advect() in five lines
With velocities in cells per unit time and stored as q[j, i]:
def advect(q, u, v, dt):
x = np.clip(I - dt*u, 0, N - 1.001) # foot, Euler backtrace, kept inside the grid
y = np.clip(J - dt*v, 0, N - 1.001)
i0, j0 = x.astype(int), y.astype(int)
s, t = x - i0, y - j0 # weights (1-s)(1-t), s(1-t), (1-s)t, st
return (1-t)*((1-s)*q[j0, i0] + s*q[j0, i0+1]) + t*((1-s)*q[j0+1, i0] + s*q[j0+1, i0+1])
Line one is the backtrace with the Euler foot; lines two and three pick the neighbours; line four is the weights and line five the maximum principle. Stam’s published code (from memory) also uses an Euler backtrace and clamps the foot just inside a ghost layer. The lab’s bilinear + Euler, CFL 1 button is that choice: in a solid rotation it pays mass and a centroid error of cells. Switch to RK2: and cells.
The lab
The box has cells; the dye is a sharp square (value ) and a smooth bump (peak sampled). Press jump to one revolution and read. Below: both dyes, solid rotation, CFL 1 (302 steps) unless stated.
- Bilinear + RK2. Max , min , , centroid error cells, mass . Smeared, in the right place.
- Bilinear + Euler. Max , , centroid error cells, mass . At CFL the mass is and the centroid error cells, against for RK2.
- Nearest cell. Max (nothing is blended), but , centroid error cells, mass : rounding every foot loses drifts under half a cell per step.
- Cubic, unclamped. Max , min , . Cubic, clamped: max , , mass .
- BFECC. Unclamped: max , min , . Clamped: max , , mass . MacCormack, clamped: , mass .
- The CFL slider. Bilinear + RK2 at CFL (603 steps), (151), (60), (30) and (15): , , , , . The max never exceeds and the min never drops below .
- Spiral flow, : mass of the start.
Computing it
A smooth Gaussian on a grid, one revolution in steps (CFL ). The solution gives error and mass ratio with RK2, and and with Euler (predicted ). The RK2 peak falls from to . With RK2, and give and : more steps smear more.
Concept checks
Problems
A foot lands at fractional position inside a cell. (a) Write the four weights. (b) Compute the variance this step adds, in cells squared. (c) For which feet is the added variance zero, and which maximise it?
Show worked solution
(a) , , , . They sum to . (b) : . : . Total cells. (c) Zero at (foot on a cell centre): whole-cell shifts are exact. The maximum is at .
A solid rotation is run with steps per revolution, . Find, for an Euler and for an RK2 backtrace, the radius factor after one revolution, and the Euler mass factor and angle lag (assume exact interpolation).
Show worked solution
Euler: , so the radius factor is and the mass factor . Angle per step , so the lag is rad . RK2: , so the radius factor is .
Evaluate the four Catmull-Rom weights at . (a) Check they sum to and that . (b) Interpolate the data at nodes and compare with bilinear interpolation between the two middle nodes. (c) What does the clamp return?
Show worked solution
(a) , , , ; the sum is , and . (b) Cubic: , an overshoot of . Bilinear between the middle nodes gives exactly . (c) The clamp uses the two nodes nearest the foot, range , and returns .
What comes next
Stam’s step is: add forces, diffuse, project, advect. Advection is now yours, with its bill: bounded and stable at any Courant number, but smeared, with mass only approximately kept. Diffusion has the same shape of problem: an explicit step needs , and Stam escapes it by solving a linear system. The next lesson, implicit methods and Crank-Nicolson (10.4), puts the diffusion term at the new time level: backward Euler is stable at any step, Crank-Nicolson is second order in time but can ring at large steps, and the system is tridiagonal in 1D (the Thomas algorithm). Solving the sparse 2D systems is the topic of 10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR (10.8).
Key Takeaways
- A semi-Lagrangian step is : backtrace, then interpolate. In a rotation the Euler foot gains in radius per step; RK2 is of order .
- Euler reads the picture at radius , so dye spirals inward: with 60 steps per revolution the radius falls to and the mass to (lab: ).
- Bilinear weights are non-negative products: a maximum principle, stable at any CFL, at a cost of variance cells squared per step (bump peak predicted , lab ).
- Bigger steps smear less in total until the backtrace error wins ( , , at CFL , , ).
- Catmull-Rom cubic adds no variance but has negative weights: sharper ( against on the bump) and overshooting (, on the square); a clamp restores .
- MacCormack and BFECC use half the round-trip error as a correction; the limiter adds mass (, ), and clamped BFECC is no better than clamped cubic at CFL .
- Mass is not conserved, even in rotation; in compression the method solves and loses mass by design ( against ).
- Next: implicit diffusion (10.4), Stam’s other half.