Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Condition estimation — where it appears

Bounding the norm of an inverse from a handful of solves with a factorisation already in hand, which every library does in place of computing it.

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

Also named here as counterexample, lower bound — the same set of essays touches all of them, so they are one junction rather than several.

the estimator maximises this quantity over the columns it visitscolumn 1 ‹visited›12column 2 ‹the answer›114column 311.4column 411.4column 511.4column 611.4column 711.4column 811.4column 911.4column 1011.4column 1111.4column 1211.4estimate 12.0a walk that stopped earlythe estimate returned12the true 1-norm114columns visited1products with the matrix5the walk's own stopping test firedand every column it could see was smaller

An estimate that can be fooled

Nobody computes a condition number, because forming an inverse costs more than the solve did. Every library estimates it instead, from four or five products with a factorisation already in hand. The estimate is exactly right on four random matrices out of five — and there is a matrix, three distinct entries wide, on which it returns a twentieth of the truth.

error · condition estimation 171319253137434910⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110²indexmagnitude|r_kk|σ_kone factorisation, two verdicts‖AP − QR‖/‖A‖1.1·10⁻¹⁶|r_nn|8.7·10⁻⁴σ_min3.7·10⁻¹²column interchanges0|r_nn| is never below σ_minso the cheap verdict errs one way only

The cheap rank and what it cannot see

Almost nobody computes singular values to decide a rank. The standard substitute is QR with column pivoting, read off the diagonal of R — and there is a triangular matrix on which the greedy rule makes no interchange at all, has no better column available at any step, and reports a matrix eight orders of magnitude further from singular than it is.

spectra · rank

Named alongside it

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

CounterexampleLower boundColumn pivotingCondition numberHilbert matrixHouseholder reflectionKahan's matrixLU factorisationMatrix normNumerical rankQR factorisationRank-revealing QR

All concepts