Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Grid complexity — where it appears

The total number of unknowns over all levels of a hierarchy divided by the number on the finest. It is one of the two numbers that say whether a multigrid method is actually optimal, the other being the operator complexity.

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

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

Named alongside it

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

Galerkin coarse operatorAlgebraic multigridCoarse fine splittingCondition numberFill-inFive-point stencilFourier modesGraph laplacianOperator complexityProlongationRestrictionRotated anisotropy

All concepts