Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Low-rank update — where it appears

A change to a matrix of rank one or a few, for which the solution can be corrected rather than recomputed — at the old matrix's conditioning. It inherits the conditioning of the object it routes through rather than of the problem it answers, which is why a downdate can be far worse than the update it undoes.

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

10¹10³10⁵10⁷10⁹10¹¹10¹³10¹⁵10⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1κ₂(A), the matrix that was updatedrelative forward errorSherman–Morrisondirect solve of A + uvᵀone answer, two routesκ of the answer's matrix1κ of the matrix replaced10·10¹³update formula's error2.5·10⁻⁴direct solve's error1.1·10⁻¹⁶the question's condition number is 1at every point on this axis

A correction cheaper than the problem

Sherman and Morrison's formula updates a solved system for a rank-one change to the matrix, at 4n² operations instead of (2/3)n³. It is exact algebra. On a problem whose updated matrix is the identity — condition number one, the easiest system there is — it returns a forward error of 2.5·10⁻⁴ where a direct solve returns 10⁻¹⁶.

leastsquares · Low-rank update 110¹10²10³10⁴10⁵10⁶10⁷10⁻¹⁷10⁻¹⁶10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸1/(1 − h), the leverage of the removed row‖R̄ᵀR̄ − (G − aaᵀ)‖ / ‖G − aaᵀ‖downdatedrefactorisedat h = 1 − 10⁻⁷κ of the downdated matrix4.3κ of the matrix downdated9.3·10⁶rotation's amplification344downdate residual3.5·10⁻¹⁰a hyperbolic rotation is not orthogonaland that is exactly what it is for

The observation that cannot be removed

Removing a rank-one term from a Cholesky factor needs a rotation that is not orthogonal, and the number under its square root is 1 − h, where h is the leverage of the row being removed. The algorithm's breakdown condition and the statistician's warning are the same quantity, arrived at from opposite ends, and neither field states it in the other's language.

leastsquares · Low-rank update 10²10³10⁴10⁻¹⁷10⁻¹⁶10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²steps taken‖RᵀR − AᵀA‖ ⁄ ‖AᵀA‖the bound, linear in the steps√k · uevery step safe, the chain notdrift after the run3.9·10⁻¹⁴the bound there3.3·10⁻¹³√k · u there6.1·10⁻¹⁵worst single amplification2.7worst leverage met0.69refreshes1backward stable onceand three thousand times is a different claim

Stable once, and three thousand times

A sliding window adds a row and removes one at every step and never looks at the data again. No single step of it amplifies by more than 2.72, no downdate fails, and after three thousand steps the triangular factor in memory is 3.9·10⁻¹⁴ from the matrix it is supposed to be a factor of — six hundred times growth from a per-step bound that says nothing about chains.

sequence · Sequence stability the smallest perturbation of any kind — 1.89·10⁻¹⁷the smallest Toeplitz one — 2.65·10⁻¹³both exact for the same x̂smallest of any kind1.9·10⁻¹⁷smallest Toeplitz one2.7·10⁻¹³the price of the constraint1.4·10⁴diagonal defect, unconstrained0.97an exact answer to a nearby problemof a kind nobody posed

A nearby problem of the wrong kind

A good algorithm returns the exact answer to a nearby problem. A hundred and eighteen essays have measured the distance and not one has asked what the nearby problem looks like. On a Toeplitz system it is a rank-one matrix that is constant along none of its diagonals — and the smallest one that is Toeplitz is two and a half million times larger.

structure · Structured backward error 10²10³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹steps takenlargest relative error in a coefficientcarried factorrecomputedcarried + one correction+ a second correctionHouseholder QR, same rowsdrift of the factorafter 2875 stepsκ(A) of the window2·10⁴carried factor2.8·10⁻⁸recomputed5.8·10⁻⁹carried + one correction7.1·10⁻¹³+ a second correction3.7·10⁻¹²Householder QR, same rows1.1·10⁻¹²measured against the coefficients in exact rationalsthe refresh repairs the factor, not the answer

The repair the drift did not need

A sliding window's carried Cholesky factor drifts 3.9·10⁻¹⁴ from its data, and multiplying by κ(AᵀA) predicts eight lost digits in the coefficients, a stream conditioned at 10¹² losing the answer, and a periodic refresh of the factor as the default repair. Measured against coefficients computed exactly in rationals, all three come out differently. On a stream made ill-conditioned by scaling, the conditioning never reaches the coefficients. On a collinear stream, a freshly recomputed factor is as wrong as the drifted one. And one correction from the window's own rows reaches Householder's accuracy for a fraction of a refresh's cost.

sequence · Sequence stability 10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹10³10⁵σ — how far the periodic wrap is from singularrelative forward error10⁻¹10⁻²10⁻³10⁻⁴10⁻⁵10⁻⁶10⁻⁷10⁻⁸10⁻⁹10⁻¹⁰10⁻¹¹10⁻¹²periodic correctionκ(C)·uelimination on Tn = 64, median of five answersperiodic correction, σ = 10⁻⁸1.2·10⁻⁴elimination on T, σ = 10⁻⁸1.1·10⁻¹⁴κ(C) at σ = 10⁻⁸4·10⁸κ(T) at σ = 10⁻⁸1712the same matrix T in every columnonly the wrap it is solved through changes

The circulant the problem did not contain

A matrix that differs from a circulant in two corner entries can be solved through the circulant, by a transform and a two-by-two correction, and the cost claim is exact. The accuracy claim is not. On tridiag(−1, 2 + σ, −1), whose condition number stops at 1,712, the correction is wrong by 1.2·10⁻⁴ at σ = 10⁻⁸ while elimination is right to 1.1·10⁻¹⁴ — because the periodic neighbour is singular at σ = 0 and the two-by-two system inherits that. Solved by Cramer's rule, as here, the two amplifications multiply; a later measurement found that a pivoted solve of the same two-by-two system removes the second.

structure · Circulant at σ = 10⁻⁸Cramer's rule1.2·10⁻⁴pivoted2.9·10⁻¹⁰elimination on T1.1·10⁻¹⁴cancellation × u1.7·10⁻¹⁰-10-9-8-7-6-5-4-3-210⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1σ, as a power of tenforward errorCramer's rulepivotedcancellation × uelimination on Tleft: σ small, the wrap nearly singularthe pivoted solve follows the cancellation

The correction lost to its own two-by-two solve

Solving a band matrix through a circulant and a small correction was measured losing the answer to 10⁻⁴ where elimination kept it to 10⁻¹⁴, and a wrap that landed one sample on a zero was measured costing four orders more than one that landed a pair. Both measurements solved the two-by-two correction system by Cramer's rule. Solved with a row interchange, the corrected solve on the same matrix loses 2.9·10⁻¹⁰ — the cancellation, and nothing multiplied onto it — and the single landing costs what the pair costs. The loss was in the determinant.

structure · Circulant 110¹10²10³110¹10²10³the accumulating quantity, relative to its first valuethe error, relative to its first valuethe bounds: slope 1what all three do: slope ½three mechanisms, one exponenta left-to-right sum0.49a chain of rotations0.55a residual recurrence0.51every bound's slope1spread of the three0.067a bound is a sum of the roundingsand the roundings have signs

Three walks and one bound

A left-to-right sum, a chain of three thousand rotations and a conjugate gradient residual recurrence share no arithmetic and no vocabulary. Each has a standard bound that is linear in whatever it accumulates against. All three come out at a half — 0.486, 0.554 and 0.507 — and nothing is rescaled.

arithmetic · Summation noise none, mediansthe answer's step0fresh start, corrected6.2·10⁻⁹carried start, corrected1.3·10⁻¹¹0200400600800100010⁻¹²10⁻¹⁰10⁻⁸steps along the streamlargest relative coefficient errorfresh solve, one correctioncarried answer, one correctionfresh solve, two correctionsHouseholder on the rowseach correction contracts its start by the same factorthe nearer start wins

The answer the last window left

A sliding window that corrects its least-squares answer at every step could start each correction from the previous step's corrected answer instead of from a fresh solve: the two windows share all but one row. On a stream with any noise in it, that start is three orders worse. The window's exact answer moves by 0.79 of itself in one step at κ(A) = 3·10⁶, a fresh seminormal solve is wrong by only 1.8·10⁻⁴, and one correction contracts either start by the same factor — so the fresh start ends at 2.2·10⁻⁸ and the carried one at 3.7·10⁻⁵. Only on data that agree exactly does carrying win.

sequence · Sequence stability n = 64, twist of half a stepnearest sample, Laplacian0.0024nearest sample, squared5.8·10⁻⁶κ(wrap), squared2.8·10⁶10⁻³10⁻²10⁻¹110⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹θsymbolπ/nLaplacian, θ² near 0its square, θ⁴ near 0no twist puts a sample further than π/n from θ = 0and the symbol's order decides what it sees there

A zero no twist can step around

Solved through its circulant wrap with the small capacitance system factorised stably, a banded matrix was found to lose only what the cancellation in the correction costs, and a twist of half a step kept that cancellation near one. That holds only while the cancellation is large. With it kept small, the corrected solve's error is a quarter of the wrap's condition number times u on every case measured — and on a symbol with a zero of fourth order, the square of the Laplacian, no twist can keep the wrap well conditioned, because the nearest sample any twist can reach sees (π/n)⁴. At n = 64 the corrected solve is 34 times less accurate than elimination, where the Laplacian's is four.

structure · Circulant at n = 128refined ÷ elimination, n = 1281.4unrefined ÷ elimination3310²10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸matrix size nrelative errorκ(wrap)·ucorrectedeliminationafter one stepthe wrap grows as n⁴ and so does the corrected errorone step puts it on elimination's line

One step past the zero

The squared Laplacian, solved through its twisted circulant and a rank-four correction, lost 6 to 34 times more accuracy than elimination, because its symbol's fourth-order zero keeps the wrap as ill conditioned as the matrix whatever the twist. One step of iterative refinement — a residual formed with the band itself, a second solve by the same route — takes it to 0.59, 0.68, 0.73 and 1.40 times elimination's error at n = 16, 32, 64 and 128, and the second and third steps go no lower. The loss the zero imposed was the solver's, and a solver's loss is what refinement removes.

structure · Circulant κ(A) = 3.22·10⁶predicted ÷ fresh, noise 10.15predicted ÷ carried, noise 0110⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴noise in the response, relative to the rowslargest relative error010⁻⁶10⁻⁴10⁻²1carried, one correctionfresh, one correctionpredicted, one correctionfresh, two correctionszero noise drawn at the leftthe update takes the better of both starts

The step the two rows owe

A sliding least-squares window can start each step's correction from a fresh solve or from the answer it already has. The answer it has is three orders worse on noisy data, because the exact answer moves by most of itself in a step. The proposal was a start that moves too: the previous answer plus the change the entering and leaving rows imply, two triangular solves from the factor the window keeps. Its start lands exactly where one correction of the carried answer lands — the update is that correction, computed from two rows instead of twenty-four — and one correction after it ends 2.9 to 440 times below the fresh start at κ(A) = 3·10⁶, and level with the carried answer when the data agree exactly.

sequence · Sequence stability

Named alongside it

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

Backward errorCondition numberIterative refinementExact ground truthCapacitance matrixCholesky factorisationCirculant matrixSymbolCondition squaringLeverageRecursive least-squaresSherman morrison woodbury

All concepts