Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Triangular solve — where it appears

Solving a system whose matrix has zeros above or below the diagonal, by substitution. It is the step that turns a factorisation into an answer, it costs a square rather than a cube, and it is where a sparse factor's fill is actually paid for.

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

nothing8.3%the right-hand side16.5%the matrix, slowly85.9%everything100.0%what can be reused: the answerwhat can be reused: the factorisationwhat can be reused: the factorisation, for a whilewhat can be reused: nothingshare of the cost of a sequence that shares nothingwhat 12 members cost in factorisationssame: factorisations1rhs: factorisations1drift: factorisations4independent: factorisations12what changes between the membersdecides what may be carried

The problem that arrives again

A hundred and thirty essays have solved a system once and measured how wrong the answer was. Almost no computation is shaped like that. A solve is one step of an outer loop, its answer is an input rather than a deliverable, and four quantities treated here as accuracy requirements turn out to be assets with a shelf life.

sequence · Sequence of solves 024681012141618202210⁶10⁷10⁸members served by one factorisationmultiplications for the whole sequencedoes not convergethe contraction ruledrift 0.01 a memberevery member1.6·10⁷every 5 members9.3·10⁶contraction rule9.2·10⁶its factorisations4cliff at a period of20a factorisation has a shelf lifeand the cliff is past the optimum

A factorisation kept past its date

One Cholesky factor can serve five members of a drifting sequence and save 44 per cent of the work. Kept for twenty it does not lose accuracy — it stops converging altogether. The optimum and the cliff are four members apart, both move with the drift, and a rule written in a ratio the iteration has already computed finds them without being told what the drift is.

sequence · Reuse 567891010⁴10⁵10⁶10⁷10⁸10⁹log₂ nmultiplicationsdense factorisation, n³⁄3the recursion, countedwhere the format starts payingratio at n = 641.5ratio at n = 5120.16exponent, first doubling2.1exponent, last doubling1.7backward error1.4·10⁻¹⁰cheaper is a sizenot a property

Where the format starts paying

A hierarchical solve costs 1.48 times a dense factorisation at 64 unknowns and 0.16 times it at 512. The crossover is between 64 and 128, it walks right when the accuracy is tightened, and the exponent between consecutive sizes is 2.13, 1.93, 1.74 — falling towards one and never arriving.

cost · Hierarchical solve A6×6B6×6I ⊗ A + Bᵀ ⊗ I36×36one equation, two objectsentries in A and B72entries in the coefficient matrix1296two routes, relative gap1.7·10⁻¹⁶‖AX + XB − C‖/‖C‖1.4·10⁻¹⁶the small squares are the problemand the large one is the notation

The elimination the matrix does not need

The Kronecker form of AX + XB = C is dismissed with a hundred million entries and (2/3)n⁶ operations. Both price an elimination, and after the reduction both routes take, the matrix has exactly n³ nonzeros, none of them above the block diagonal, and nothing left to eliminate.

structure · Matrix equation deepest barrier, far well right to within halfno exponent limit40gradual, started at 102433fp16, gradual underflow23fp16, flush to zero13051015202530354010⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹barrier depth, octaves below the near wellrelative error in the far well's masssmallest normalsmallest subnormalno exponent limitgradual, started at 1024fp16, gradual underflowfp16, flush to zeroan error of one: the far well is emptysubnormals bought nine octaves

The well on the far side of the band

Gradual underflow was said to buy a predicate and not an answer, because a quantity that has decayed into the subnormal range is already lost. A quantity that passes through the band on its way somewhere else is not. The stationary distribution of a two-well chain, computed in half precision across a barrier whose top is two to the minus sixteen of the near well, keeps its far well's probability of 0.2454 to three digits with subnormals and returns exactly zero without them. The normwise backward error calls both answers exact.

arithmetic · Subnormals

Named alongside it

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

Flop countBackward errorCholesky factorisationExact ground truthNewton iterationWarm startAsymptotic analysisBidiagonal matrixBlock methodsChord methodComponentwise condition numberCondition number

All concepts