All demos

Numerical methods

One character of code

Two particle simulations, the same swirling field, the same step size. One reads x1 instead of x in a single line, and its dye stays exactly as even as it started, however long it runs. The other clumps.

Clumping index: the variance of particle counts over a 64 × 64 grid divided by their mean. Particles scattered independently and uniformly give about 1; bunching drives it up. Both panels start from the same random cloud and use the same field and step size.

What you’re watching

Same field, same step, one line apart

Each panel is a square of fluid that wraps around at its edges, filled with 262,144 particles on a desktop GPU (65,536 on phones and small screens). Both panels start from the same random cloud and are stirred by the same field, a few sine waves whose phases drift so the swirls wander. The dye colour is fixed by where each particle started, so the stripes stretch into filaments as the flow mixes them.

The only difference is the second line of the update. Forward Euler reads the up-down push at the particle’s old x; the shear update reads it at the new x1. Switch to Density to see the clumps and voids without the dye, change the step size, or restart both panels from the same even cloud.

In our test runs on a desktop at the default settings, forward Euler’s clumping index passed 1,000 within about 900 steps (15 seconds) and kept swinging between roughly 800 and 2,800. The shear panel’s stayed between 0.96 and 1.04 for the whole run of 2,800 steps.

Explainer

Why one character keeps the dye even

Pick a level with the switch on the diagram: Curious has no symbols, Builder has the code and the algebra, Mathematician has the statements. The pictures are the same at every level.

1 / 9
  1. The question

    These are the same two simulations as above, small enough to watch side by side. Both stir the same coloured dots with the same swirling pattern and the same size of step. The red number under each measures clumping: 1 means the dots are as evenly spread as if you had sprinkled them at random.

    On the left the number creeps up and the dots bunch into bright threads. On the right it stays at 1. The two programs differ by one character. Why should that matter?

  2. The stir

    This is the stirring pattern. Each arrow shows which way the water at that spot is pushed. Split it into two pushes. The sideways push is the same all along any row: it only changes as you go up or down. The up-and-down push is the same all along any column.

    Now look at the highlighted box. Whatever is pushed in through its left side is pushed out of its right side at exactly the same rate, because both sides sit in the same rows. Top and bottom work the same way. Nothing piles up inside. That is what it means for water to be incompressible, one box at a time.

  3. Euler’s step

    A computer can’t move the dots smoothly; it moves them in small jumps. The obvious recipe is to look at both pushes where the dot is now, then jump.

    Follow the white grain. It reads the sideways push at its starting point, reads the up-and-down push at its starting point too, and jumps by both at once.

  4. The leak

    Now follow a tiny square of water through ten of those jumps. It tilts and stretches, which is fine: real water does that. But watch the purple number. The square’s area changes. At each jump some squares grow a little and others shrink.

    Run that for thousands of jumps over hundreds of thousands of dots and they drain out of the growing places and pile into the shrinking ones. That is the clumping on the left.

  5. One character

    Here is the fix, and it really is tiny. Do the jump in two halves. First slide the grain sideways, exactly as before. Then, for the up-and-down slide, read the push at the place the grain has just moved to, not where it started.

    Same pushes, same size of jump, same amount of work. The grain lands a little away from where the obvious recipe would put it (the faint ring), and that small difference turns out to be everything.

  6. A deck of cards

    Why does that work? Look at the first half-step on its own. Every row slides sideways by its own amount, like pushing a deck of cards so that it leans. The deck changes shape, but each card keeps its length, so the deck covers exactly the same area. The second half-step does the same with columns. Watch the purple number.

  7. Mixing without squeezing

    So the shear version can stir as hard as it likes. The dye folds into finer and finer threads, but the dots never bunch: the red number hugs 1 for as long as you watch.

    Mixing and squeezing turn out to be different things. Real stirring mixes without squeezing, and now the simulation does too.

  8. Name it

    That’s the whole idea. Sliding rows can’t change area, sliding columns can’t either, and doing one after the other can’t, however big the slides. In the jargon: shears preserve area exactly.

  9. Why physics engines do this

    The trick is everywhere. Swing a pendulum in a game using the obvious recipe and it slowly gains energy until it whirls over the top. With the two-half-steps recipe it keeps swinging steadily. Each loop on the stage is one pendulum, drawn as its position against its speed.

The theorem

Shears preserve area, exactly

Let T2=R2/Z2\mathbb{T}^2 = \mathbb{R}^2/\mathbb{Z}^2 carry Lebesgue measure μ\mu. For Borel-measurable 1-periodic f,g:R→Rf, g : \mathbb{R}\to\mathbb{R} define the shears

Sf(x,y)=(x+f(y), y),Rg(x,y)=(x, y+g(x))(mod1),S_f(x,y) = \bigl(x + \gold{f}(y),\ y\bigr),\qquad R_g(x,y) = \bigl(x,\ y + \blue{g}(x)\bigr)\pmod 1,

and T=Rg∘SfT = R_g\circ S_f. (The demo’s update is the case hf,hghf, hg, which are again Borel and 1-periodic.)

(a) TT is a bijection of T2\mathbb{T}^2 and μ(T−1B)=μ(B)\mu(T^{-1}B) = \mu(B) for every Borel set BB.

(b) If T1,T2,…T_1, T_2, \dots are maps of this form, each with its own (fn,gn)(f_n, g_n), and P1,…,PMP_1,\dots,P_M are independent and uniform on T2\mathbb{T}^2, then for every nn the points Tn∘⋯∘T1(Pi)T_n\circ\cdots\circ T_1(P_i) are again independent and uniform.

(c) By contrast, let v=(ψy,−ψx)v = (\psi_y, -\psi_x) for a smooth 1-periodic ψ\psi, and let E(p)=p+h v(p)E(p) = p + h\,v(p) with h>0h > 0 be one forward-Euler step. Then det⁡DE=1+h2K\det DE = 1 + h^2K with K=ψxxψyy−ψxy2K = \psi_{xx}\psi_{yy} - \psi_{xy}^2, and if K≢0K\not\equiv 0 then for every hh with 0<h Lip(v)<10 < h\,\mathrm{Lip}(v) < 1 the map EE (mod Z2\mathbb{Z}^2) is injective on T2\mathbb{T}^2 but does not preserve area. For the demo’s field v=(f(y),g(x))v = (\gold{f}(y), \blue{g}(x)) one has ψ=F(y)−G(x)\psi = F(y) - G(x) and K=−f′(y) g′(x)K = -f'(y)\,g'(x), so Euler’s Jacobian is 1−h2f′(y) g′(x)1 - h^2 f'(y)\,g'(x).

Read the proof

(a) Shears preserve area

SfS_f is well defined on T2\mathbb{T}^2 because ff is 1-periodic, so the formula does not depend on the representative of yy, and replacing xx by x+1x+1 changes the output by (1,0)≡(0,0)(1,0)\equiv(0,0). It is a bijection with inverse (x,y)↦(x−f(y), y)(x,y)\mapsto(x - f(y),\ y), well defined for the same reason. Likewise RgR_g is a bijection with inverse (x,y)↦(x, y−g(x))(x,y)\mapsto(x,\ y - g(x)). Both maps and their inverses are Borel measurable, being compositions of the Borel map (x,y)↦(x,f(y),y)(x,y)\mapsto(x, f(y), y) with continuous addition.

Let BB be a Borel set and, for y∈[0,1)y\in[0,1), let By={x∈R/Z:(x,y)∈B}B^y = \{x\in\mathbb{R}/\mathbb{Z} : (x,y)\in B\} be its horizontal slice. The horizontal slice of Sf−1(B)={(x,y):(x+f(y),y)∈B}S_f^{-1}(B) = \{(x,y) : (x + f(y), y)\in B\} at height yy is By−f(y)B^y - f(y), a translate of ByB^y on the circle. Translation preserves Lebesgue measure λ\lambda on R/Z\mathbb{R}/\mathbb{Z}, and Sf−1(B)S_f^{-1}(B) is Borel, so by Tonelli’s theorem

μ(Sf−1(B))=∫01λ(By−f(y)) dy=∫01λ(By) dy=μ(B).\mu\bigl(S_f^{-1}(B)\bigr) = \int_0^1 \lambda\bigl(B^y - f(y)\bigr)\,dy = \int_0^1 \lambda(B^y)\,dy = \mu(B).

The same argument with vertical slices gives μ(Rg−1(B))=μ(B)\mu(R_g^{-1}(B)) = \mu(B). Hence μ(T−1B)=μ(Sf−1(Rg−1B))=μ(Rg−1B)=μ(B)\mu(T^{-1}B) = \mu\bigl(S_f^{-1}(R_g^{-1}B)\bigr) = \mu(R_g^{-1}B) = \mu(B). No smallness of ff or gg and no differentiability is needed.

(b) Uniform clouds stay uniform

Let Φn=Tn∘⋯∘T1\Phi_n = T_n\circ\cdots\circ T_1. By (a) applied repeatedly, Φn\Phi_n is a Borel bijection with μ(Φn−1B)=μ(B)\mu(\Phi_n^{-1}B) = \mu(B) for every Borel BB. If PP is uniform then Pr⁡(Φn(P)∈B)=Pr⁡(P∈Φn−1B)=μ(Φn−1B)=μ(B)\Pr(\Phi_n(P)\in B) = \Pr(P\in\Phi_n^{-1}B) = \mu(\Phi_n^{-1}B) = \mu(B), so Φn(P)\Phi_n(P) is uniform. The maps are deterministic, so for Borel B1,…,BMB_1,\dots,B_M, using independence of the PiP_i,

Pr⁡(Φn(Pi)∈Bi ∀i)=Pr⁡(Pi∈Φn−1Bi ∀i)=∏iμ(Φn−1Bi)=∏iμ(Bi).\Pr\bigl(\Phi_n(P_i)\in B_i\ \forall i\bigr) = \Pr\bigl(P_i\in\Phi_n^{-1}B_i\ \forall i\bigr) = \prod_i\mu(\Phi_n^{-1}B_i) = \prod_i\mu(B_i).

So the images are independent and uniform.

(c) Forward Euler does not

The Jacobian matrix of EE is I+hMI + hM with M=∇v=(ψxyψyy−ψxx−ψxy)M = \nabla v = \begin{pmatrix}\psi_{xy} & \psi_{yy} \\ -\psi_{xx} & -\psi_{xy}\end{pmatrix}. For any 2 × 2 matrix, det⁡(I+hM)=1+htr⁡M+h2det⁡M\det(I + hM) = 1 + h\operatorname{tr}M + h^2\det M. Here tr⁡M=0\operatorname{tr}M = 0 and det⁡M=ψxxψyy−ψxy2=K\det M = \psi_{xx}\psi_{yy} - \psi_{xy}^2 = K, so det⁡DE=1+h2K\det DE = 1 + h^2K.

Injectivity. Lift EE to R2\mathbb{R}^2 by the same formula; vv is Z2\mathbb{Z}^2-periodic. For p≠p′p\neq p', ∣E(p)−E(p′)∣≥∣p−p′∣−h∣v(p)−v(p′)∣≥(1−h Lip(v)) ∣p−p′∣>0|E(p) - E(p')| \ge |p - p'| - h|v(p) - v(p')| \ge (1 - h\,\mathrm{Lip}(v))\,|p - p'| > 0. If E(p)=E(p′)+nE(p) = E(p') + n with n∈Z2n\in\mathbb{Z}^2, then E(p)=E(p′+n)E(p) = E(p' + n) by periodicity of vv, so p=p′+np = p' + n. Hence EE is injective on T2\mathbb{T}^2.

Positive Jacobian. For every pp and unit vector ww, ∣Mw∣=∣Dv(p) w∣≤Lip(v)|Mw| = |Dv(p)\,w| \le \mathrm{Lip}(v), so ∥M∥≤Lip(v)\|M\| \le \mathrm{Lip}(v) and h∥M∥<1h\|M\| < 1. Since tr⁡M=0\operatorname{tr}M = 0, Cayley–Hamilton gives M2=−(det⁡M) I=−K IM^2 = -(\det M)\,I = -K\,I, so ∣K∣≤∥M∥2|K| \le \|M\|^2. Therefore 1+h2K≥1−h2∥M∥2>01 + h^2K \ge 1 - h^2\|M\|^2 > 0 everywhere.

Area is not preserved. Suppose K(p0)≠0K(p_0)\neq 0. By continuity KK has a constant nonzero sign on an open disc Ω~⊂R2\tilde\Omega\subset\mathbb{R}^2 of diameter less than 1 around a lift of p0p_0; its projection Ω\Omega is an isometric copy, so μ(Ω)=area⁡(Ω~)\mu(\Omega) = \operatorname{area}(\tilde\Omega). The lifted EE is C1C^1 and injective on Ω~\tilde\Omega with Jacobian 1+h2K>01 + h^2K > 0, so by the change-of-variables formula area⁡(E(Ω~))=∫Ω~(1+h2K) dA\operatorname{area}(E(\tilde\Omega)) = \int_{\tilde\Omega}(1 + h^2K)\,dA, which is strictly larger or strictly smaller than area⁡(Ω~)\operatorname{area}(\tilde\Omega) according to the sign of KK. By the injectivity on the torus, the projection R2→T2\mathbb{R}^2\to\mathbb{T}^2 is injective on E(Ω~)E(\tilde\Omega) (if E(p)≡E(p′)E(p)\equiv E(p') with p,p′∈Ω~p, p'\in\tilde\Omega then p≡p′p\equiv p', and p=p′p = p' because Ω~\tilde\Omega has diameter less than 1), so μ(E(Ω))=area⁡(E(Ω~))≠μ(Ω)\mu(E(\Omega)) = \operatorname{area}(E(\tilde\Omega)) \neq \mu(\Omega). E(Ω)E(\Omega) is open by the inverse function theorem, hence Borel. Take B=E(Ω)B = E(\Omega): injectivity gives E−1(B)=ΩE^{-1}(B) = \Omega, so μ(E−1B)=μ(Ω)≠μ(B)\mu(E^{-1}B) = \mu(\Omega)\neq\mu(B), and EE does not preserve area in the sense of (a). ■\blacksquare

For the demo’s field, v=(f(y),g(x))v = (f(y), g(x)) with f,gf, g of mean zero is (ψy,−ψx)(\psi_y, -\psi_x) for ψ=F(y)−G(x)\psi = F(y) - G(x) with F′=fF' = f, G′=gG' = g periodic. Then ψxx=−g′(x)\psi_{xx} = -g'(x), ψyy=f′(y)\psi_{yy} = f'(y), ψxy=0\psi_{xy} = 0, so K=−f′(y) g′(x)K = -f'(y)\,g'(x), which is not identically zero for any non-constant ff and gg.

Adversarially reviewed by four independent AI verifiers. One flagged unstated steps (injectivity, measurability); the proof was rewritten to state them and four further verifiers found no hole.