Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Relative error — where it appears

An error divided by the size of the quantity it is an error in, which is the only form comparable across the twenty orders of magnitude here. It is the only comparable form across the twenty orders of magnitude here, and relative to what is a question a badly scaled problem answers differently.

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

10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹xrelative error of the computed value(1 − cos x)/x², as written2 sin²(x/2)/x²no digits left at allbinary64 throughoutone function, two spellings · zero below 1.5·10⁻⁸

Cancellation takes the answer, not a digit

Subtracting two nearly equal numbers is exact. That is what makes it dangerous — the subtraction introduces no error at all, it exposes error the operands were already carrying, and the exposure can consume every significant figure at once.

arithmetic · Cancellation 10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1relative size of the entrywise perturbationrelative forward errorκ∞ · εcond(A,x) · εmeasuredboth bounds holdκ∞(A)1.9·10⁸cond(A, x)4.8ratio of the bounds4·10⁷both curves above the data are boundsand only one of them is a measurement

A condition number scaling cannot move

Skeel's componentwise condition number is invariant under any row scaling — exactly, before any norm is taken, because two diagonal factors cancel entry by entry. It is never larger than the normwise one and can be arbitrarily smaller, and the ratio between them is a diagnostic for which kind of ill-conditioning a matrix has.

error · Scaling 10⁻⁷10⁻⁵10⁻³10⁻¹⁰10⁻⁸10⁻⁶magnitudespacing to the next numberthe smallest normalgradualflush to zerosmallest normal6.1·10⁻⁵smallest subnormal6·10⁻⁸octaves of subnormals10pairs that lie under FTZ10the spacing stops halving and stays putwhich is what makes x − y = 0 mean x = y

The numbers below the smallest one

Below the smallest normal number the spacing stops halving and stays put, all the way to zero. That is what gradual underflow is, and the thing it buys is the sentence every algorithm assumes without being told — x minus y is zero only when x equals y.

arithmetic · Subnormals 048121610⁻⁸10⁻⁷10⁻⁶10⁻⁵extra columns in the sample, prelative compression errorthe best rank-8 representationfive draws, mean and rangea band, not a lineexcess at p = 012excess at p = 83spread at p = 00.44spread at p = 80.12the optimum of this rank7.8·10⁻⁸one seed shows the meanand five show the risk

What a single draw cannot report

With no oversampling the construction's error is 11.6 to 50 times the best representation of the same rank, and the spread across five seeds runs from 16 to 146 per cent of the mean. Sixteen extra columns bring the excess to between 2.0 and 2.9 at every rank measured and the spread to between 4 and 20 per cent — and the second number is the one a single run cannot report and the one that decides whether the first is a measurement.

randomised · Sketching 234567891010⁻⁴10⁻²1ADI steps krelative error, and max|r|²max|r|²the measured errora bound that is an identitysteps drawn9ratio, worst0.77spread of the ratio1error at k = 103.9·10⁻⁴its residual1.1·10⁻⁴four orders of errorand one constant

Bracketing an error nobody can measure

The error of a low-rank Gramian factor is the one quantity a caller cannot compute, because computing it needs the Gramian the factor exists to avoid forming. Two numbers that can be computed sit either side of it — a rational factor known before the run, and a residual known after — and they stay a factor of four apart across a fourfold change of size.

reduction · Gramian decay entries rounded to zero, of 320block, as given310block, sorted by size22E4M3, either order0median entry's relative errorblock, as given1block, sorted0.00321E4M30.022the same numbers, three waysdeleted, as given310deleted, sorted22deleted, per-element08-bit significands, blocks of 32sorting is free and changes no value

A bit buys an octave

The outlier a block survives is exactly two raised to its significand width — 8 at three bits, 32 at five, 128 at seven, 512 at nine. Each extra bit doubles the range the block tolerates and halves the ordinary entry's error. Reordering the same numbers buys every octave at once and costs nothing.

arithmetic · Block formats 24 bits, κ² 10⁶one-pass ÷ κ²u7.7compensated ÷ κ²u0.92Welford ÷ κu0.067two-pass, in u6.5110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10¹⁶κ² = 1 + mean² ÷ variancerelative error ÷ uevery digit goneκ²uone-passcompensated or pairwiseWelfordshifted by x₁two-passdashed purple: κ²u, the digits-lost rulethe formula sets the power of κ

The formula sets the power, the sum sets the constant

The one-pass variance was found losing three to sixty-nine times more than the digits-lost rule allows, and the explanation offered — operands built from a thousand roundings — was never priced. Measured against the exact variance of the stored data, the rule's ratio is the variance's own condition number squared, and the formula decides what power of it the error grows with: two for every one-pass variant, one for Welford's update, none for two passes or a shift. The summation decides only the constant in front — about 0.4√n for running sums, one for pairwise or compensated ones — and the sixty-nine was neither: it belonged to the random numbers.

arithmetic · Cancellation 16243240485664728010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴order nerrormiddle eigenvalues, errormiddle eigenvectorsworst eigenvector, componentwiseworst eigenvector, normwisefloored at 10⁻¹⁷the middle is the best of the spectrum

The middle eigenvectors come back exact

The Sylvester–Kac matrix's eigenvectors are known exactly, and the middle ones were predicted to be lost before their eigenvalues, since the gap between neighbouring eigenvalues is only two. Started from the all-ones vector, inverse iteration seems to confirm it: half the middle eigenvectors are wholly wrong at order 80 while their eigenvalues keep five digits. But the all-ones vector has, in exact arithmetic, no component at all along every other eigenvector. From a random start the middle eigenvectors come back exact to fourteen digits at every order measured, while their eigenvalues lose up to eleven. What is lost is at the ends of the spectrum, in the smallest entries of eigenvectors whose entries span twenty decades — and never by more than three units of roundoff times that span.

error · Exact ground truth 01020304050607010⁻⁶10⁻³110³10⁶10⁹k‖Aᵏ/k!‖‖e^A‖ = 2.6largest term 1.4·10⁷what the series throws awaylargest term1.4·10⁷‖e^A‖2.6digits cancelled away5.4·10⁶error after the sum5.2·10⁻⁹every term is computed correctlyand the sum has lost seven digits

The error the method already knows

Summing the exponential's Taylor series throws away a known number of digits, and the number is on the machine while the sum is being formed. The largest term divided by the answer, times the unit roundoff, tracks the relative error that comes out — to within a factor of nine, across fourteen orders of magnitude of it — and nothing reports it.

spectra · Matrix function

Named alongside it

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

Forward errorCatastrophic cancellationCondition numberBackward errorExact ground truthSignificandStable formulationUnit roundoffADI iterationBlack box constructionBlock floating pointCancellation

All concepts