Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

M-matrix — where it appears

A matrix with nonpositive off-diagonals and a nonnegative inverse, which is what makes a discrete solution obey a maximum principle. It is what guarantees a discrete maximum principle, and losing it is what turns a plausible discretisation into one that oscillates.

Named by 7 essays across one field — each of them below, with the objects they name alongside it.

point · strong in y0.951point · strong in x0.956y-line · strong in y0.037y-line · strong in x0.967semi-y · strong in y0.107semi-y · strong in x0.9661.00 — no convergenceone problem, seen from two sidesy-line, aimed0.037y-line, turned sideways0.97the ratio2631×31 grid, twelve V-cyclesthe direction is in the code, not in the problem

Coarsening in one direction only

Leave the smoother alone and halve only the strong direction, and the smoothing factor is 0.3340 — identical to line relaxation's, at every anisotropy and every weight, to twelve digits. The convergence factors are then a factor of three apart, and at 45° both repairs fail outright.

iterative · Anisotropy the grid the operator came froman edge is a coupling the matrix calls strongkeptinterpolatedwhat the entries decidedcoupling ratio, x against y0.001strong couplings across x0strong couplings along y110rows kept or dropped whole1111×11 grid, θ = 0.25the coarse grid, from the matrix alone

The coarse grid the matrix chooses

Given a tridiagonal matrix and no information about a grid, the coarsening keeps every other point and derives the weights ½, 1, ½ — the operators the geometric method was handed. Given the anisotropic operator, it discovers semi-coarsening, in the right direction, without a coordinate.

iterative · Algebraic multigrid 00.250.50.75100.250.50.751xuexactcentral differencesupwindthe oscillation is exact‖Ax − b‖/‖b‖ for the central answer4.6·10⁻¹⁸values outside [0, 1]16worst excursion0.52the dashed lines are 0 and 1, which the equation guaranteesno solver was involved

The stencil that is not symmetric

Past a cell Péclet number of exactly one — measured by bisection at 1.0000000000000002 — the central-difference solution of a convection–diffusion problem oscillates from point to point and leaves the interval the equation guarantees, at 16 of 31 grid points. It is the exact solution of its own linear system, to 4.6·10⁻¹⁸. No solver was involved.

iterative · Convection 00.250.50.75100.51xuexact & tunedupwindcentralone of these is exacttuned, worst nodal error2.4·10⁻¹⁷upwind, worst nodal error0.14central, points outside [0, 1]16exact at every nodeand only at the nodes

The diffusion that makes the answer exact

Upwinding adds h/2 of artificial diffusion. Central differencing adds none. Add ε·ξ·Pe with ξ = coth(Pe) − 1/Pe and the computed solution is the exact one at every grid point, to 2.4·10⁻¹⁷ — at every Péclet number, on the problem it was derived from and on no other.

iterative · Convection worst nodal error, and nodes outside the interval the equation guarantees0°, streamline only2.39·10⁻¹⁷ · 0 outside0°, with crosswind5.25·10⁻¹⁷ · 0 outside15°, streamline only0.032 · 18 outside15°, with crosswind0.0145 · 9 outside30°, streamline only0.0571 · 50 outside30°, with crosswind0.0247 · 11 outside45°, streamline only0.0661 · 48 outside45°, with crosswind0.0281 · 0 outsidewhat the crosswind term buyserror ratio at 0°0.45error ratio at 15°2.2error ratio at 30°2.3error ratio at 45°2.3free where the scheme was exactand half the error everywhere else

The direction the diffusion does not go

Streamline diffusion adds τbbᵀ, a rank-one tensor that annihilates every direction across the flow. That is the design. The price is 18, 50 and 48 nodes where the computed solution leaves the interval the equation guarantees — and half a coefficient of crosswind diffusion halves the error at every angle while costing exactly nothing where the scheme was exact.

iterative · Convection 00.250.50.75100.250.50.751xuexact at ε = 0.005exact at ε(1 + Pe)the upwind answeran exact answer to a different question‖upwind(ε) − central(ε(1+Pe))‖/‖·‖0distance to the problem it solves0.026distance to the problem posed0.36the added diffusion is h/2 = 0.001953, whatever ε isso refining removes it

A different equation on every grid

Upwinding is the exact discretisation of a convection–diffusion problem with diffusion ε + h/2, entry for entry, at a relative difference of between 0 and 1.26·10⁻¹⁶ on every mesh from 15 points to 511. The equation it is exact for is chosen by the mesh and not by ε — the added diffusion is 0.01563 on a 31-point grid whether ε is 0.2 or 0.001.

iterative · Convection 00.7853981.57082.356193.1415900.250.50.751frequency θdamping |g(θ)|the oscillatory half →⅓ — the symmetric optimumno convectionwith convectionits imaginary parta modulus, not a valuesmoothing factor at this ω0.71best over every ω0.71the symmetric operator's, at ω = 2/30.33the imaginary part does not depend on ωso no ω removes it

A smoother that stops being one

Weighted Jacobi's smoothing factor on the convection–diffusion operator is a function of the cell Péclet number and nothing else — identical to eight digits at five grid sizes at matched Pe. It is 0.3335 at Pe = 0.016, exactly 1/√2 at Pe = 1, and 5.2190 at Pe = 7.8, where the sweep amplifies the modes it exists to remove.

iterative · Multigrid

Named alongside it

The objects these essays reach for when they reach for this one.

Convection diffusionPeclet numberArtificial diffusionUpwind differencingBoundary layerSmoothing factorAnisotropyDiscretisationProlongationSemi-coarseningStreamline diffusionThe V-cycle

All concepts