Flow Lab

Syllabus / Module 10: Numerical Methods for PDEs

Lesson 10.7

Semi-Lagrangian Advection

Stam's key idea: trace particles backward and interpolate. Unconditional stability, interpolation choices, MacCormack/BFECC corrections.

Written byClaude Sonnet

🌊
Why this matters for simulation: This is the 'advect' step of Stable Fluids, built from scratch.

By the end of this lesson you can…

  • Trace a 2D foot with an Euler or RK2 backtrace and predict, for solid-body rotation, the radius and angle error per revolution.
  • Write the four bilinear weights, prove the maximum principle from them, and compute the variance a step adds.
  • Explain why cubic (Catmull-Rom) interpolation sharpens and overshoots, and why a clamp restores the bounds.
  • Describe MacCormack and BFECC error correction, and say what the limiter protects and what it costs.
  • Show that semi-Lagrangian advection does not conserve mass, and measure the drift in rotation and compression.
  • Implement 2D semi-Lagrangian advection with bilinear interpolation and measure the error after one revolution.
On this page
·
  1. The backtrace in 2D
  2. Reading between cells: bilinear weights
  3. Cubic interpolation: sharper, and not bounded
  4. Error correction: MacCormack and BFECC
  5. Mass is not conserved
  6. Stam’s advect() in five lines
  7. The lab
  8. Computing it
  9. Concept checks
  10. Problems
  11. What comes next
  12. Key Takeaways

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 3.163.16 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.

▶ Video Backtracing a rotating flow, bilinear and cubic interpolation of a square, the Euler foot spiralling inward, BFECC with and without its limiter, and the mass that is not conservedcaptions only
Transcript
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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 x\mathbf x is the old value at the foot of its characteristic, the place the arriving parcel stood one step earlier:

qn+1(x)=qn(xfoot),xfoot=x−Δt u(x)    (Euler),xfoot=x−Δt u(x−12Δt u(x))    (RK2, midpoint).q^{n+1}(\mathbf x) = q^n(\mathbf x_{\text{foot}}), \qquad \mathbf x_{\text{foot}} = \mathbf x - \Delta t\,\mathbf u(\mathbf x) \;\;\text{(Euler)}, \qquad \mathbf x_{\text{foot}} = \mathbf x - \Delta t\,\mathbf u\big(\mathbf x - \tfrac12\Delta t\,\mathbf u(\mathbf x)\big) \;\;\text{(RK2, midpoint)}.

These are the Euler and midpoint steps of 4.3 Runge–Kutta Methods & Butcher Tableaux, run with step −Δt-\Delta t. The test flow is solid-body rotation about the centre of a unit box, u=−ω(y−12)u = -\omega(y - \tfrac12), v=ω(x−12)v = \omega(x - \tfrac12), ω=2π\omega = 2\pi. After exactly one revolution (time 11) the exact answer is the starting picture, so every difference belongs to the method.

Let θ=ωΔt\theta = \omega\Delta t and let d\mathbf d be the position relative to the centre. The Euler foot is d−θJd\mathbf d - \theta J\mathbf d, where JJ turns a vector by 90∘90^\circ. The vectors d\mathbf d and JdJ\mathbf d are perpendicular and equally long, so

∣d−θJd∣=1+θ2 ∣d∣,foot angle=arctan⁡θ    (not θ).\lvert \mathbf d - \theta J\mathbf d\rvert = \sqrt{1+\theta^2}\,\lvert\mathbf d\rvert, \qquad \text{foot angle} = \arctan\theta \;\;(\text{not } \theta).

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 n=2π/θn = 2\pi/\theta steps the radius is multiplied by (1+θ2)−n/2(1+\theta^2)^{-n/2} and the angle lags by 2π−narctan⁡θ≈nθ3/32\pi - n\arctan\theta \approx n\theta^3/3. The midpoint foot is d−θJd+12θ2J2d=(1−θ22)d−θJd\mathbf d - \theta J\mathbf d + \tfrac12\theta^2J^2\mathbf d = (1 - \tfrac{\theta^2}{2})\mathbf d - \theta J\mathbf d, with length 1+θ4/4 ∣d∣\sqrt{1+\theta^4/4}\,\lvert\mathbf d\rvert: the radius error is fourth order in θ\theta, and the angle leads by about θ3/6\theta^3/6 per step.

The lab grid has 96×9696\times96 cells and quotes the Courant number at radius 12\tfrac12: CFL=πNΔt\mathrm{CFL} = \pi N\Delta t. At CFL≈5\mathrm{CFL}\approx5 (60 steps per revolution, θ=0.1047\theta = 0.1047) the formulas give, per revolution:

backtraceradius factorangle error
Euler0.72090.7209lag 1.31∘1.31^\circ
RK20.99910.9991lead 0.66∘0.66^\circ

At the node 0.2450.245 from the centre the Euler foot misses the exact one by 0.245(1+θ2−1)=0.1290.245(\sqrt{1+\theta^2}-1) = 0.129 cells per step, the RK2 foot (the lab’s foot function against the exact foot) by 0.00450.0045. Run the smooth bump alone (dye: smooth bump only, bilinear) for one revolution at CFL 5.035.03: the centroid error reads 6.7136.713 cells with Euler and 0.2750.275 with RK2. The inward creep predicted for the bump (radius 0.250.25) is 0.25 (1−0.7209)=6.700.25\,(1 - 0.7209) = 6.70 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 (s,t)(s, t), each in [0,1)[0,1). Bilinear interpolation blends the four surrounding values with weights

(1−s)(1−t),s(1−t),(1−s)t,st.(1-s)(1-t),\qquad s(1-t),\qquad (1-s)t,\qquad st .

All four are at least 00 and they sum to [(1−s)+s][(1−t)+t]=1[(1-s)+s][(1-t)+t] = 1. A weighted average with non-negative weights cannot leave the range of what it averages, so min⁡qn≤qn+1≤max⁡qn\min q^n \le q^{n+1} \le \max q^n however far the foot sits. That is the maximum principle (10.3 Von Neumann Stability Analysis writes it as ∣G∣≤1\lvert G\rvert \le 1) and the whole stability proof. In the lab, bilinear dye never leaves [0,1][0, 1] at any CFL from 0.50.5 to 2020.

What it costs. The weights have a spread. In xx the variance is s(1−s)s(1-s) cells squared, in yy it is t(1−t)t(1-t), and since the weights are products, xx and yy are uncorrelated. Each step adds that variance to the picture, as a diffusion step does. A Gaussian of variance σ2\sigma^2 per axis loses peak height like σ2/σfinal2\sigma^2/\sigma^2_{\text{final}} in 2D.

The lab’s bump has σ2=0.0018\sigma^2 = 0.0018 per axis. At CFL 11 (302302 steps) it sits at radius 0.250.25 and moves 0.50.5 cells per step, in a direction that turns once around, so the xx offset is 0.5∣cos⁡ϕ∣0.5\lvert\cos\phi\rvert cells and the mean of a(1−a)a(1-a) over the circle is 0.5⋅2π−14⋅12=0.19330.5\cdot\tfrac2\pi - \tfrac14\cdot\tfrac12 = 0.1933. Per axis that adds 302×0.1933 h2=0.00633302\times0.1933\,h^2 = 0.00633, so σfinal2=0.00813\sigma^2_{\text{final}} = 0.00813 and the peak falls to 0.0018/0.00813=0.2210.0018/0.00813 = 0.221 of its starting height (0.9850.985 as sampled, so 0.2180.218). The lab (bilinear, RK2, bump only, one revolution) reads max 0.22640.2264, within 4%4\%. Summing s(1−s)+t(1−t)s(1-s)+t(1-t) along the bump’s path at CFL 55 (a short script) predicts 0.6000.600; the lab reads 0.61300.6130.

Bigger steps smear less in total: fewer interpolations. With the full pattern (bilinear, RK2) the L2L_2 error after one revolution is 0.13570.1357 at CFL 11, 0.08270.0827 at 55 and 0.07500.0750 at 1010; then the foot error takes over, and CFL 2020 gives 0.13630.1363.

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 −1,0,1,2-1, 0, 1, 2 from the foot’s lower neighbour, with weights (fraction ff)

w−1=12(−f3+2f2−f),w0=12(3f3−5f2+2),w1=12(−3f3+4f2+f),w2=12(f3−f2),w_{-1} = \tfrac12(-f^3 + 2f^2 - f),\quad w_0 = \tfrac12(3f^3 - 5f^2 + 2),\quad w_1 = \tfrac12(-3f^3 + 4f^2 + f),\quad w_2 = \tfrac12(f^3 - f^2),

and a 2D value is the tensor product, sixteen cells. At f=12f = \tfrac12 the weights are −116,916,916,−116-\tfrac1{16},\tfrac9{16},\tfrac9{16},-\tfrac1{16}. First, their spread about the foot is ∑wkk2−f2=14−14=0\sum w_k k^2 - f^2 = \tfrac14 - \tfrac14 = 0: 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 11, RK2). Smooth bump alone: bilinear L2L_2 error 0.052610.05261, cubic 0.0055500.005550, minimum only −0.006965-0.006965. Sharp square alone: cubic reaches max 1.2161.216, min −0.1782-0.1782, against 0.66630.6663 and ≈0\approx0 for bilinear, with L2L_2 error 0.061420.06142 against 0.12510.1251.

A clamp restores the bounds: clip the result to the minimum and maximum of the four nearest cell values. On the square: max 1.00001.0000, min 00, L2L_2 0.066200.06620, mass 1.88%1.88\% 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 AA be one advection step. Compute

q^=A(q),q~=A−1(q^),error estimate 12(q−q~),\hat q = A(q), \qquad \tilde q = A^{-1}(\hat q), \qquad \text{error estimate } \tfrac12(q - \tilde q),

where A−1A^{-1} is advection by the reversed flow. If AA were exact, q~=q\tilde q = q. Each pass smooths, so q−q~q - \tilde q is about twice one step’s damage. Two ways to use the estimate:

  • MacCormack (from memory): qn+1=q^+12(q−q~)q^{n+1} = \hat q + \tfrac12(q - \tilde q). Two advections, correction added at the end.
  • BFECC (back and forth error compensation and correction, from memory): advect the corrected field, qn+1=A(q+12(q−q~))q^{n+1} = A\big(q + \tfrac12(q - \tilde q)\big). Three advections.

Both are second order on smooth data (from memory), and neither is monotone. The limiter is the clamp above: clip qn+1q^{n+1} to the range of the four old values around the foot.

At CFL 11, bilinear, RK2, square alone (the lab’s numbers, 302 steps): plain bilinear has L2L_2 0.12510.1251 and max 0.66630.6663. BFECC unclamped reaches L2L_2 0.062940.06294 with max 1.1921.192 and min −0.1589-0.1589. With the clamp, max 1.0001.000, min 00 and L2L_2 0.067690.06769, and the mass is 2.03%2.03\% above the start. Clamped cubic, one advection with sixteen reads, gave 0.066200.06620 and 1.88%1.88\%: 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: L2L_2 0.09480.0948 clamped against 0.06810.0681 for clamped BFECC, and +5.65%+5.65\% mass against +1.57%+1.57\%. At CFL 2020 neither helps: clamped BFECC reads 0.13870.1387 against 0.13630.1363 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 d↦d−θJd\mathbf d \mapsto \mathbf d - \theta J\mathbf d has Jacobian determinant 1+θ21+\theta^2 and samples a larger area each step, so mass is multiplied by (1+θ2)−n(1+\theta^2)^{-n} per revolution. With the full pattern and bilinear interpolation:

settingmass drift after one revolution
Euler, CFL 1 (302 steps)−12.16%-12.16\% (predicted factor 0.87750.8775)
Euler, CFL 5.03 (60 steps)−48.03%-48.03\% (predicted factor 0.51980.5198)
RK2, CFL 1+0.04%+0.04\%
RK2, CFL 20 (15 steps)−10.86%-10.86\%

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 u−=s d\mathbf u \mathrel{-}= s\,\mathbf d, s=0.5s = 0.5, so ∇⋅u=−2s=−1\nabla\cdot\mathbf u = -2s = -1. Semi-Lagrangian advection solves Dq/Dt=0Dq/Dt = 0: qq keeps its values while the area it covers shrinks as e−2sTe^{-2sT}. After one revolution (bilinear, RK2, CFL 11) the lab reads mass 0.36760.3676 of the start, against e−1=0.3679e^{-1} = 0.3679 for that equation. If qq is a density, the right equation keeps the mass and 63%63\% 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 qq 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 −12.16%-12.16\% mass and a centroid error of 0.8680.868 cells. Switch to RK2: +0.04%+0.04\% and 0.0130.013 cells.

The lab

◆ Interactive A square and a bump carried once around by a rotating flow: choose interpolation, backtrace, error correction and CFL, and read the overshoot, mass and error

Loading simulation…

The box has 96×9696\times96 cells; the dye is a sharp square (value 11) and a smooth bump (peak 0.9850.985 sampled). Press jump to one revolution and read. Below: both dyes, solid rotation, CFL 1 (302 steps) unless stated.

  1. Bilinear + RK2. Max 0.66630.6663, min ≈10−8\approx 10^{-8}, L2L_2 0.13570.1357, centroid error 0.0130.013 cells, mass +0.04%+0.04\%. Smeared, in the right place.
  2. Bilinear + Euler. Max 0.64800.6480, L2L_2 0.13930.1393, centroid error 0.8680.868 cells, mass −12.16%-12.16\%. At CFL 5.035.03 the mass is −48.03%-48.03\% and the centroid error 3.9383.938 cells, against 0.1620.162 for RK2.
  3. Nearest cell. Max 1.0001.000 (nothing is blended), but L2L_2 0.17480.1748, centroid error 11.97111.971 cells, mass −32.69%-32.69\%: rounding every foot loses drifts under half a cell per step.
  4. Cubic, unclamped. Max 1.2161.216, min −0.1782-0.1782, L2L_2 0.061670.06167. Cubic, clamped: max 1.0001.000, L2L_2 0.066520.06652, mass +1.41%+1.41\%.
  5. BFECC. Unclamped: max 1.1921.192, min −0.1589-0.1589, L2L_2 0.063240.06324. Clamped: max 1.0001.000, L2L_2 0.068060.06806, mass +1.57%+1.57\%. MacCormack, clamped: L2L_2 0.094800.09480, mass +5.65%+5.65\%.
  6. The CFL slider. Bilinear + RK2 at CFL 0.50.5 (603 steps), 22 (151), 55 (60), 1010 (30) and 2020 (15): L2L_2 0.14720.1472, 0.10560.1056, 0.08270.0827, 0.07500.0750, 0.13630.1363. The max never exceeds 1.00001.0000 and the min never drops below 00.
  7. Spiral flow, s=0.5s = 0.5: mass 0.36760.3676 of the start.

Computing it

🧪 Coding exerciseExercise: 2D semi-Lagrangian advection, one revolution, Euler against RK2
⌘/Ctrl + Enter

A smooth Gaussian on a 48×4848\times48 grid, one revolution in 4848 steps (CFL π≈3.14\pi\approx3.14). The solution gives L2L_2 error 0.03780.0378 and mass ratio 0.99980.9998 with RK2, and 0.09690.0969 and 0.44530.4453 with Euler (predicted (1+θ2)−n=0.4424(1+\theta^2)^{-n} = 0.4424). The RK2 peak falls from 0.99220.9922 to 0.6840.684. With RK2, n=24n = 24 and n=96n = 96 give L2L_2 0.02720.0272 and 0.06400.0640: more steps smear more.

Concept checks

✅ Concept check

A foot lands exactly half a cell from the nearest cell centre in both directions, $(s, t) = (0.5, 0.5)$. With bilinear interpolation, how much variance (in cells squared) does this step add to the picture?

✅ Concept check

Solid-body rotation with an Euler backtrace and bilinear interpolation. What happens to the dye over one revolution?

✅ Concept check

Why can a clamp-free cubic (Catmull-Rom) step push a square pulse above its original maximum, when a bilinear step never does?

Problems

✏️ Pen & paperBilinear weights and the variance of one step●○○

A foot lands at fractional position (s,t)=(0.25,0.5)(s, t) = (0.25, 0.5) 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) (1−s)(1−t)=0.375(1-s)(1-t) = 0.375, s(1−t)=0.125s(1-t) = 0.125, (1−s)t=0.375(1-s)t = 0.375, st=0.125st = 0.125. They sum to 11. (b) xx: s(1−s)=0.1875s(1-s) = 0.1875. yy: t(1−t)=0.25t(1-t) = 0.25. Total 0.43750.4375 cells2^2. (c) Zero at s=t=0s = t = 0 (foot on a cell centre): whole-cell shifts are exact. The maximum is 0.50.5 at s=t=12s = t = \tfrac12.

✏️ Pen & paperEuler and RK2 on one revolution●●○

A solid rotation is run with n=30n = 30 steps per revolution, θ=2π/30=0.2094\theta = 2\pi/30 = 0.2094. 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: θ2=0.04386\theta^2 = 0.04386, so the radius factor is (1.04386)−15=e−15(0.042931)=0.5252(1.04386)^{-15} = e^{-15(0.042931)} = 0.5252 and the mass factor 0.52522=0.27580.5252^2 = 0.2758. Angle per step arctan⁡θ=0.206456\arctan\theta = 0.206456, so the lag is 2π−30(0.206456)=0.08952\pi - 30(0.206456) = 0.0895 rad =5.13∘= 5.13^\circ. RK2: θ4/4=0.000481\theta^4/4 = 0.000481, so the radius factor is (1.000481)−15=0.9928(1.000481)^{-15} = 0.9928.

✏️ Pen & paperCatmull-Rom at a quarter cell●●○

Evaluate the four Catmull-Rom weights at f=14f = \tfrac14. (a) Check they sum to 11 and that ∑wkk2=f2\sum w_k k^2 = f^2. (b) Interpolate the data (0,1,1,0)(0, 1, 1, 0) at nodes −1,0,1,2-1, 0, 1, 2 and compare with bilinear interpolation between the two middle nodes. (c) What does the 2×22\times2 clamp return?

Show worked solution

(a) w−1=−0.0703125w_{-1} = -0.0703125, w0=0.8671875w_0 = 0.8671875, w1=0.2265625w_1 = 0.2265625, w2=−0.0234375w_2 = -0.0234375; the sum is 11, and w−1+w1+4w2=0.0625=f2w_{-1} + w_1 + 4w_2 = 0.0625 = f^2. (b) Cubic: 0.8671875+0.2265625=1.093750.8671875 + 0.2265625 = 1.09375, an overshoot of 0.093750.09375. Bilinear between the middle nodes gives exactly 11. (c) The clamp uses the two nodes nearest the foot, range [1,1][1, 1], and returns 11.

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 r=νΔt/h2≤12r = \nu\Delta t/h^2 \le \tfrac12, 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 qn+1(x)=qn(foot)q^{n+1}(\mathbf x) = q^n(\text{foot}): backtrace, then interpolate. In a rotation the Euler foot gains θ2/2\theta^2/2 in radius per step; RK2 is of order θ3\theta^3.
  • Euler reads the picture at radius 1+θ2 r\sqrt{1+\theta^2}\,r, so dye spirals inward: with 60 steps per revolution the radius falls to 0.72090.7209 and the mass to 0.51980.5198 (lab: −48.03%-48.03\%).
  • Bilinear weights are non-negative products: a maximum principle, stable at any CFL, at a cost of variance s(1−s)+t(1−t)s(1-s)+t(1-t) cells squared per step (bump peak predicted 0.2180.218, lab 0.22640.2264).
  • Bigger steps smear less in total until the backtrace error wins (L2L_2 0.13570.1357, 0.07500.0750, 0.13630.1363 at CFL 11, 1010, 2020).
  • Catmull-Rom cubic adds no variance but has negative weights: sharper (0.005550.00555 against 0.05260.0526 on the bump) and overshooting (1.2161.216, −0.1782-0.1782 on the square); a clamp restores [0,1][0, 1].
  • MacCormack and BFECC use half the round-trip error as a correction; the limiter adds mass (+1.57%+1.57\%, +5.65%+5.65\%), and clamped BFECC is no better than clamped cubic at CFL 11.
  • Mass is not conserved, even in rotation; in compression the method solves Dq/Dt=0Dq/Dt = 0 and loses mass by design (0.36760.3676 against e−1e^{-1}).
  • Next: implicit diffusion (10.4), Stam’s other half.
Finished this lesson?

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

Where this leads

These later lessons build directly on this one: