Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Weighted jacobi — where it appears

A relaxation that moves each unknown a fraction of the way towards satisfying its own equation, used as a smoother rather than as a solver. Its weight is chosen to damp the high-frequency error a coarse grid cannot see, and the optimal value is available in closed form on the model problem.

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

00.250.50.751-1-0.500.51mode frequency θ / πdamping factor per sweeppredictedmeasured±0.333a coarse grid seestwo routes to one factorsmoothing factor, scanned0.33smoothing factor, closed form0.33worst mode disagreement4.4·10⁻¹⁶63 interior points, one sweepthe left-hand end is what the coarse grid is for

The error smoothing cannot reach

One weighted Jacobi sweep multiplies every mode of the error by a number, and the number is a sine. Half the modes are cut by three or better, and the other half come back at 0.999 — which is not a failure of the method but the fact the whole of multigrid is built on.

iterative · Multigrid θx (frequency across x)θy0π/2π0π/2πthe coarse grid'sunder 0.2under 0.40under 0.60under 0.80under 0.95under 1.01damping per sweeptwo routessmoothing factor, scanned1closed form130×30 frequency cellsthe marker is the mode nothing removes

A direction the smoother cannot see

Give the Laplacian a strong direction and multigrid stops working — from 0.2016 a cycle to 0.9565 — with every component unchanged and the condition number identical to twelve digits. The problem did not get harder. The link between the method's two halves broke.

iterative · Anisotropy 10⁻⁴10⁻³10⁻²10⁻¹100.250.50.751anisotropy εsmoothing factor μpoint + fully-line + fullpoint + semi-y⅓, the one-dimensional answertwo routes, three curvesgap between the repairs2.2·10⁻¹⁶scan against closed form2.2·10⁻¹⁶the dashed curve lies on the solid one beneath itone repair, written two ways

Smoothing a whole line at once

Solve every grid line in the strong direction exactly rather than sweeping over it, and the smoothing factor goes from 0.9993 back to 0.3340 — which is the one-dimensional answer, on a problem that is not one-dimensional. The repair replaces one ε in the closed form by a one.

iterative · Anisotropy 75 aggregates over 225 unknownsthe matrix chose thismean extent along y3mean extent along x1points adopted by pass two15no coordinate enters the methodand the shape follows the coupling

Aggregating what the matrix calls strong

The depth phase measured every method it had on the 45°-rotated anisotropic operator — 0.784, 0.883, 0.844 — and diagnosed the failure as being in the discretisation rather than in the hierarchy. Smoothed aggregation is the standard answer to anisotropy. It returns 0.789.

iterative · Anisotropy 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.

Smoothing factorAnisotropyFourier modesCondition numberThe V-cycleAlgebraic multigridBlock jacobiBoundary layerConvection diffusionDiagonal dominanceFive-point stencilGalerkin coarse operator

All concepts