Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Componentwise condition number — where it appears

The amplification factor for a perturbation that moves each entry by a fraction of itself, which is exactly invariant under any row scaling. It is the quantity a badly scaled problem's sensitivity should be measured in, and it is exactly what a row scaling cannot move.

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

-14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴3·10¹⁵its relative error10⁻¹⁵κ₂ condensed2.4·10¹⁶its relative error0.31the same step, written two waysand only one of them is solvable

A condition number sent to infinity

An interior-point method manufactures an ill-conditioned matrix on every iteration, deliberately, because the separating of a diagonal is how it discovers which constraints are active. Written one way the answer keeps fifteen digits at a condition number of 3·10¹⁵. Written the other way — the way almost every code writes it — it has none left.

constraint · Interior-point conditioning 0246810110²10⁴10⁶10⁸10¹⁰10¹²spread of the row units (decades)condition numberκ∞(DA)cond(DA)Hilbert κ∞Hilbert condone system, two numbersκ∞ at no spread9.8κ∞ at 10 decades1.9·10¹⁰cond, either end7Hilbert, equilibrated1.3·10¹⁰the solution is the same at every spreadand one of these curves knows it

The units the matrix is measured in

One linear system, written twice. The rows of the second are the rows of the first in different units, the solution is identical to the last bit, and the condition number has moved by eight orders of magnitude. One of those two numbers is a fact about the problem and the other is a fact about the notation.

error · Scaling 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 110¹10²10³10⁻¹⁸10⁻¹⁴10⁻¹⁰10⁻⁶10⁻²10²10⁶numbers that describe the matrixcondition number, and backward errordensetoeplitzsymmetricρ aloneno such problemcondition numberbackward errorone matrix, four descriptionsκ, all n² entries7.9·10⁴as one number, ρ62backward error, unconstrained2·10⁻¹⁷as a symmetric Toeplitz matrix5.6·10⁻¹²fewer numbers, better conditionedand no nearby problem left

The condition number of the model

Describe a 40×40 Toeplitz matrix by its 1,600 entries and its condition number is 78,800. Describe it by the one number it actually contains and the condition number is 61.9. The three decades in between are not an approximation or a bound — they are what κ has been over-stating, and the drop is not where the linear algebra is.

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 -12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μcondition number, and relative errorκ₂, augmentedcomponentwise, condensedcomponentwise, augmentederror, augmentedone matrix, two numbersκ₂ at μ = 10⁻¹²3·10¹³componentwise, same matrix13their ratio2.3·10¹²measured error9.4·10⁻¹⁶every library prints the top lineand the error obeys the third

Two condition numbers of one matrix

κ₂ is a worst case over perturbations of a given norm, and a normwise perturbation may put its whole budget on the smallest entry. The componentwise number is a worst case over perturbations proportional to the entries, which is what a backward-stable factorisation actually makes. On one matrix they are 3·10¹³ and 13.3, and the error obeys the second.

error · Scaling 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.

Backward errorCondition numberExact ground truthForward errorEquilibrationHilbert matrixInterior-point methodIterative refinementPerturbationRow scalingSaddle-point systemsSkeel condition number

All concepts