10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR solved for a matrix that arrived out of nowhere: on the diagonal, at four neighbours. It ended with Stam’s twenty Gauss-Seidel sweeps leaving of the error on a plate. This lesson answers the question that came before: where does that matrix come from when the unknown is a pressure that straightens a velocity? It depends on where the numbers are stored. Put , and at the same points and the natural stencils decouple the grid. Stagger them and the matrix is the five-point one, with a row for every kind of wall. 11.10 The Projection Method for Incompressible Flow and 11.11 Stam's Stable Fluids, Step by Step already lean on this layout; here we build the arrays, the rows and the boundary rules, and measure what twenty sweeps buy.
Transcript
- A MAC grid cuts the box into N by N cells. The pressure sits at each cell centre, the horizontal velocity u on the vertical faces, and the vertical velocity v on the horizontal faces. At N equal 8 that is 64 pressures and 72 values each of u and v. The faces on the walls are known, so only 112 faces are unknowns. Every difference now sits between the two values it compares.
- The divergence of a cell is the net outflow, read off its four faces. The gradient of p lives on the interior faces, as the difference of the two cells either side. Divergence of gradient, at an interior cell, is the second difference in each direction, which is exactly minus the five-point matrix over h squared. So D G equals minus A over h squared, and the sweeps of lesson 10.8 solve the pressure equation. The divergence of a discrete curl is 0 for any stream function, and G is minus the transpose of D, so A is symmetric.
- Now the alternative, with every value at the cell centres. A centred gradient skips the centre, so a checkerboard pressure has the same value at i plus 1 and i minus 1, and its gradient is exactly 0. A solver can leave any amount of it behind. On the MAC grid the gradient compares neighbours, so the checkerboard shows up as plus or minus 2 a over h on every face. At N equal 16 with a equal 0.2, the largest x gradient is 0 collocated and 6.4 on MAC. The pressure operator gives 1.39 times 10 to the minus 17, round-off, on the collocated grid, and 1.6, which is 8 a, on MAC.
- Every cell has a row in A, set by its four faces. Beside a closed wall the missing neighbour is dropped, so the diagonal counts fluid neighbours: 3 beside a wall, 2 in a corner. The row sums are zero, so the constant is a null vector, and a solution exists only if the divergences sum to zero, which says the net flux through the walls is zero. In the lab it is 2.26 times 10 to the minus 17 at N equal 8. An outlet at pressure 0 adds 2 to the diagonal, giving 5, makes the matrix non-singular, and lets flux leave: net flux 1, and the field still projects to divergence 0. Tangential velocity reads ghost cells: the interior value for free slip, minus it for no slip.
- A tiny case by hand: 2 by 2 cells. Push 1 through one face. The divergences are 2, minus 2, 0 and 0, and they sum to 0, so a solution exists. Solving gives p equal minus 3, 3, minus 1, 1, over 16. The gradients are 0.75, 0.25, 0.25 and minus 0.25. Subtract them and the push becomes a counterclockwise loop of speed 0.25, with divergence 0 in every cell.
- Now a real field: a source blob plus a swirl on closed walls, projected with 20 Gauss-Seidel sweeps from zero pressure. At N equal 32 the largest divergence starts at 16.33, and after 20 sweeps it is 3.11, on the same colour scale. The exact solve leaves 8.54 times 10 to the minus 13, which is round-off. What survives is not cell-scale noise. Gauss-Seidel removes that part fastest, and the grid-wide part of the compression is left.
- Refine the grid and the sweeps fall behind. At N equal 8 they take the largest divergence from 12.08 to 0.0344, a fraction 0.00285. At 16, from 16.03 to 0.348, a fraction 0.0217. At 32, from 16.33 to 3.11, a fraction 0.190. The uniform push is harder still, leaving 0.109, 0.184 and 0.187. The slowest Gauss-Seidel factor approaches 1 like 1 minus order h squared, so a finer grid has more grid-wide compression for 20 sweeps to miss. At N equal 32 a fifth of it is left.
- So where does this leave us? We have the layout, the stencils, the wall rows, and the measured cost of 20 sweeps: a fifth of the compression at N equal 32. The next lesson in build order is the wind-tunnel capstone, 16.1, not yet written. It assembles this projection with an inflow, an outlet and a staircase airfoil, and its bottleneck is exactly the sweeps we just measured. Multigrid, 10.9, also not yet written, is the cure, since a smooth error is a rough one on a coarser grid.
Where the unknowns live
Cut the unit box into square cells of side . On a MAC grid (marker-and-cell) each cell carries a pressure at its centre, and the velocity components sit on the faces they point through:
- at the cell centre: values;
- on the vertical face at , : values;
- on the horizontal face at , : values.
At that is pressures and values each of and . The extra column of faces and row of faces lie on the walls, where the velocity through the wall is known ( at a closed wall, the inflow speed at an inlet), so only the interior faces are unknowns, at . Every difference sits between the two values it compares: the change of across a cell belongs at the centre, the change of between centres on the face where lives.
Divergence, gradient, and the Laplacian
The divergence of a cell is net outflow per unit area, read off its four faces, and the gradient lives on the interior faces:
The projection step of 11.10 The Projection Method for Incompressible Flow wants , that is . At an interior cell the divergence takes the difference of the east gradient and the west gradient , over :
So , with the five-point matrix of 10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR. No new solver is needed: the pressure equation is , and the sweeps of 10.8 solve it. Two more facts matter later.
Curl is invisible to . Put a stream function at the cell corners and set , on the faces between them. In a cell’s divergence each of the four values appears twice with opposite signs, so exactly, for any . A discrete curl is discretely divergence-free, which is why projection keeps the swirl and removes only the compression.
Adjointness. Summing over cells and moving each difference onto gives , so is symmetric and positive semi-definite, and conjugate gradients and Gauss-Seidel apply.
The collocated grid and its checkerboard
The tempting alternative stores , , all at cell centres and differences over two cells, . 11.10 The Projection Method for Incompressible Flow derived what goes wrong; the short version follows.
The centred gradient skips the centre. A pressure has the same value at and , so its gradient is exactly zero, and subtracting a gradient cannot remove it. Centred divergence times centred gradient is the wide stencil , which links every second cell: the grid falls into four sub-grids that never talk. On a periodic box the null space has dimension (the playground computes it for ): the constant, , and the checkerboard. A solver may leave any amount of those modes in the pressure.
The MAC gradient is one cell wide. A checkerboard of amplitude gives on every face, and the five-point operator turns it into in every cell. The lab measures both at , : the largest -gradient the checkerboard makes is collocated and () on MAC, and the pressure operator applied to it gives (round-off) for the wide collocated stencil and () for MAC.
Wall rows: Neumann, Dirichlet, and the null space
Every cell has one row in , and the row depends on what its four faces are.
A closed wall. The wall face carries normal velocity and is not an unknown, so no gradient is applied there and the cell’s missing neighbour is dropped. For a cell with fluid neighbours:
The diagonal is : beside a wall, in a corner. This is the discrete Neumann condition (11.10 The Projection Method for Incompressible Flow derives it from ). The row sums are zero, so and the constant vector is in the null space. The playground builds from and at and gets rank of , smallest eigenvalue , next ().
Compatibility. Because is symmetric, for every , so a solution exists only if the right side sums to zero:
In the sum every interior face appears twice with opposite signs and only wall faces survive, so the sum times is the net flux out. With closed walls it vanishes to round-off (the lab at prints ). Feed air through an inlet with no way out and no pressure can make the velocity divergence-free. When the condition holds the solution is unique up to a constant, which changes no gradient; Gauss-Seidel and CG still converge, and most codes subtract the mean.
An outlet. A wall open to ambient air has a known pressure, taken as : a Dirichlet condition. With the face at distance from the centre, the ghost value is and the face gradient is twice an ordinary one, so the diagonal gains : a cell with the other three neighbours fluid has diagonal . The rows no longer sum to zero, so is non-singular (rank of and smallest eigenvalue at ) and there is no compatibility condition. Flux may leave: in the lab the uniform push with the right wall open has net flux out of the box and still projects to divergence .
Obstacles. A solid cell is a wall to its fluid neighbours: the shared face carries the solid’s normal velocity and the fluid row drops that neighbour, so a staircase body gives a staircase of Neumann rows. Cut cells (a glimpse, from memory) give each face an open fraction, which removes the staircase error but breaks the simple matrix structure. A tunnel with prescribed inflow and zero-gradient outflow is all-Neumann, so inflow must equal outflow; a Dirichlet outlet avoids that.
Ghost cells for the tangential velocity
The projection touches only the normal components, which live on the walls. The tangential component lives half a cell away, and wherever a stencil needs it near the wall (diffusion, 10.4 Implicit Methods & Crank–Nicolson; the interpolation inside advection) it reads a ghost cell one layer outside the box:
| boundary | normal velocity | tangential velocity (ghost value) | pressure |
|---|---|---|---|
| closed, free-slip | on the face | ghost = interior value, so | Neumann |
| closed, no-slip | on the face | ghost = minus interior value, so the wall average is | Neumann |
| inflow | prescribed on the face | prescribed (often ) | Neumann, flux matched |
| outflow | free (set by the projection) | copied (zero gradient) | Dirichlet, |
The no-slip rule is the ghost-cell device of 10.1 Finite Differences: Discretizing Derivatives applied to velocity: a ghost equal to minus its neighbour averages to zero at the wall. Stam’s set_bnd (from memory) flips the normal component at a wall and copies the rest: free slip. A no-slip wall also flips the tangential one, which is where the boundary layer of 11.8 Boundary Layers would be born if the grid could resolve it.
The lab: project a field and count what is left
The top row draws the grid: dots are pressures, cyan arrows , amber arrows , cell colour the divergence. The first panel is a source blob plus a swirl, with zero normal velocity on the walls; the second the same field after subtracting , with from Gauss-Seidel sweeps on from ; the third that pressure.
For the source field on closed walls, the largest before projection and after sweeps:
| before | after sweeps | fraction left | |
|---|---|---|---|
The exact solve (conjugate gradients to ) leaves , and : round-off. The uniform push (every interior equal to ) is harder: it starts at and sweeps leave , and , so , and of it.
This is the mechanism of 10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR on a real divergence: Gauss-Seidel removes the cell-scale part fastest, and the grid-wide part survives, which a finer grid has more of because the slowest factor approaches like . At twenty sweeps do nearly all the job; at they leave a fifth of the compression.
The bottom row is the checkerboard: the exact pressure plus , then its -gradient as a collocated grid computes it (the checkerboard has vanished) and on the MAC faces (a stripe pattern of amplitude that the solver cannot ignore).
Worked example: a box by hand
Take , , cells along the bottom and along the top. Each cell has two fluid neighbours, so every diagonal is :
The unknown faces are two faces on and two faces on . Set on the bottom face and everything else to . The divergences are in cell (flow leaves to the right), in cell , and elsewhere: they sum to , so a solution exists. The right side is . By the antisymmetry , the rows reduce to and , so , , and with mean zero
The gradients are (bottom face), (top face), (left face) and (right face). Subtracting, becomes (bottom) and (top), becomes (left) and (right). Cell now has divergence , and so do the others: the one-face push has become a counterclockwise loop of speed . The playground checks it.
Playground: assemble and
The exercise
Implement the MAC divergence and the discrete curl, and test the identities above.
Concept checks
Problems
For count the pressures, the and values and the unknown faces, and give the shapes of , and (wall faces kept in the face list).
Show worked solution
Pressures ; and each , so face values; unknown faces of each kind, . is , is (zero rows for wall faces), is with at most five nonzeros per row.
A closed one-dimensional duct has cells, , and face velocities . Find , the divergences and the pressure, and verify that the projected velocity is zero. Then set the last face to and show the system has no solution.
Show worked solution
The end cells have one fluid neighbour and the middle cell two, so . Divergences: , , , summing to . The right side is . Row 1 gives , row 3 gives , and row 2 holds. The gradients and equal the interior velocities, so . With the right side is . The rows of add to zero, the right side to : no pressure exists.
On a periodic collocated grid, show that with centred differences has eigenvalue on , find its null space, and compare with the MAC eigenvalue .
Show worked solution
In one direction gives , zero at and . In 2D both sines must vanish: , four modes, , , , . The MAC eigenvalue is zero only at , and the checkerboard has its largest, .
What comes next
The course was not built in syllabus order: 11.10 and 11.11 already exist and assume this grid. The next lesson in build order is the 2D virtual wind tunnel capstone (16.1 Capstone: 2D Virtual Wind Tunnel, 16.1), which is assembly rather than new theory: this MAC projection with an inflow, an outlet and a staircased airfoil, plus semi-Lagrangian advection (10.7 Semi-Lagrangian Advection) and implicit diffusion (10.4 Implicit Methods & Crank–Nicolson). The bottleneck is the one measured above: twenty cold-start sweeps leave a fifth of the divergence at , and more on finer grids, so the capstone needs a better solver or must accept the loss. Multigrid (10.9 Multigrid) is the cure.
Key Takeaways
- On a MAC grid sits at cell centres, on vertical faces and on horizontal faces (, and values at ); each divergence or gradient uses only adjacent values.
- The MAC divergence times the MAC gradient is exactly the five-point Laplacian, , and the divergence of a discrete curl is zero for any stream function.
- Centred differences on a collocated grid skip the centre, so has gradient and the periodic wide operator has a null space of dimension . On MAC the same checkerboard has face gradient ( at , ).
- A closed wall drops the missing neighbour: the diagonal counts fluid neighbours, the constant is a null vector (rank of at ), and a solution needs the cell divergences to sum to zero, which closed walls guarantee.
- An outlet at adds to the diagonal, makes non-singular and lets flux leave; a solid cell is a wall to its neighbours.
- Tangential velocity uses ghost cells: the interior value for free-slip, minus it for no-slip.
- Exact solves leave round-off ( to in the lab); twenty cold-start sweeps leave , and of the source field’s divergence at .
- Next: the wind-tunnel capstone (16.1 Capstone: 2D Virtual Wind Tunnel) assembles these pieces; multigrid (10.9 Multigrid) addresses sweeps that stop short.