Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Contraction factor — where it appears

The factor by which one step of a fixed-point iteration is expected to reduce the distance to its answer. For iterative refinement it is the norm of Id minus the inner solver's approximate inverse applied to the matrix, so it is set by how good the factorisation is as a preconditioner for the problem actually being solved rather than by how far the first answer was from the last.

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

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 01234510⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1correction steprelative errorLU route: η = 2.2·10⁻¹⁷LU route: forward 2.8·10⁻⁴forward errorbackward errorwhat a correction buysη before refinement4.5·10⁻⁵η after four steps2.8·10⁻¹⁷forward, unchanged7.1·10⁻⁴cost of a step, flops1800the residual is repairableand the accuracy floor is the problem's

The gap refinement can close

Multiplying by a computed inverse is not backward stable, and refinement at the working precision repairs it. That much is settled. The claim beside it — that the forward error does not move — was read at one conditioning and four corrections too late. Swept over ten, it moves at every one, and it lands on the LU route's own number after a single correction.

elimination · Inversion

Named alongside it

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

Backward errorCholesky factorisationChord methodCondition numberExact ground truthFlop countForward errorIterative refinementLinear convergenceMatrix inverseNewton iterationResidual

All concepts