Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Algebraic multigrid — where it appears

A multigrid method that builds its coarse levels from the matrix entries rather than from a grid, and so needs no geometry. It works where no grid exists, and everything it needs — the coarse variables, the interpolation, the coarse operator — has to be inferred from the entries rather than looked up.

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

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 01234567110¹10²levelstored entries per rowalgebraicgeometrictwo complexities, one hierarchygrid complexity3.1operator complexity18geometric, for comparison1.5a ring plus random chords — nothing is anywherelevel 6 is 100% dense

A hierarchy with no grid behind it

On a graph Laplacian the algebraic V-cycle converges at 0.199 a cycle, its grid complexity is an unremarkable 3.05, and its operator complexity is 17.7 — one level of forty-one unknowns is entirely dense. The number people quote is the one that does not measure the work.

iterative · Algebraic multigrid 081624324000.250.50.7511.25angle of the strong direction (degrees)ratio, and convergence factorenergy ratio of oneenergy ratioclassicalminimiserwith the constraintwhere the formula is optimalenergy ratio at 0°1energy ratio at 45°1.2classical rate at 45°0.35the minimiser's rate there0.28a ratio of exactly one while the assumption holdsand a diagnostic when it stops

The formula that was already optimal

Ask for the interpolation that minimises the energy of its own columns and the answer is the classical AMG formula — to zero at every row of the one-dimensional Laplacian, and to four digits in two dimensions. On the operator rotated to 45° the two part company, and the gap between them is a diagnostic that needs no reference solution.

iterative · Algebraic multigrid 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 10⁻¹100.20.40.60.8strength threshold θresidual reduction per cycleθ = εsemi-coarseningkept whole rowsfull coarseningone parameter, two methodsbest factor above ε0.053best factor below ε0.1the ratio across the switch231×31 anisotropic operatora switch, not a dial

The switch does not know which side is better

The strength threshold moves the coarsening from full to semi at θ = ε exactly, at every anisotropy. Which of the two converges faster is a separate question with a separate answer, and it changes sign between ε = 0.33 and ε = 0.34 — where nothing whatever happens to the switch.

iterative · Algebraic multigrid

Named alongside it

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

Strength of connectionAnisotropyCoarse fine splittingGalerkin coarse operatorOperator complexityInterpolation weightsNear-null spaceRotated anisotropySemi-coarseningA normCoarse grid correctionConstrained minimisation

All concepts