Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Galerkin coarse operator — where it appears

The coarse matrix formed as PᵀAP from an interpolation operator P. It is what makes an algebraic hierarchy possible without a grid, and its density is what an operator complexity measures.

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

15731pointsfinest gridone unknown — the recursion bottoms out in a divisionthe coarse operator, two ways‖RAₕP − A₂ₕ‖/‖A₂ₕ‖10⁻¹⁸unknowns / finest grid1.7cycle cost, in fine sweeps12each coarse point reaches three fine ones½, 1, ½ — and the restriction is its transpose

The same problem on a coarser grid

Restriction, the coarse operator and interpolation are three matrices with nine distinct entries between them. Two of the three are each other's transpose, and their product with the fine operator is the coarse discretisation exactly — not approximately, entry for entry, at every level.

iterative · Multigrid -0.0833-0.167-0.0833-0.1671-0.167-0.0833-0.167-0.0833R · A · P, normalised to a unit centrestored entries per rowlevel 0 · 31×314.87/rowlevel 1 · 15×158.22/rowlevel 2 · 7×77.37/rowlevel 3 · 3×35.44/rowlevel 4 · 1×11.00/rowstill a stencil, still annihilates a constantentries in an interior row9weight outside the 3×30row sum0the isotropic model problemnine, at every level below the first

The coarse problem is a different problem

In one dimension the Galerkin coarse operator is the coarse discretisation, entry for entry — this site asserted it. In two dimensions a five-point operator produces a nine-point coarse one, so the recursion solves a different discretisation at every level below the first, and converges at 0.20 a cycle regardless.

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 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 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.

Algebraic multigridAnisotropyCoarse fine splittingFourier modesProlongationStrength of connectionThe V-cycleCondition numberFive-point stencilGrid complexityOperator complexityRestriction

All concepts