Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Kahan's matrix — where it appears

An upper triangular matrix with sⁱ down the diagonal and −c·sⁱ above it, on which every trailing column norm is exactly equal at every step. It is built from one parameter c in (0, 1) with s the root of 1 − c², it gives a greedy pivot rule nothing to choose between, and its smallest singular value falls far below the last diagonal entry a factorisation reports.

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

81930415263110²10⁴10⁶10⁸10¹⁰10¹²size of the matrix|r_nn| ÷ σ_minthe two agreec = 0.2c = 0.35c = 0.5no ceilingratio at n = 1021ratio at n = 646.8·10¹⁰interchanges, anywhere0the greedy rule never had a choiceand the gap grows with every row

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 1611162126313610⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹indexmagnitude|r_kk|σ_kone factorisation, two verdicts‖AP − QR‖/‖A‖10⁻¹⁵|r_nn|1.1·10⁻¹²σ_min10·10⁻¹³column interchanges33|r_nn| is never below σ_minso the cheap verdict errs one way only

A good curve and a bad verdict

The diagonal of a column-pivoted R is famous for the one matrix it is wrong about. On that matrix it is right about thirty-nine of its forty entries — every |r_kk| within a factor of six of the σ_k it stands for — and wrong by 4·10⁶ at the fortieth, which is the only one a rank verdict ever reads.

spectra · Rank

Named alongside it

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

Column pivotingCounterexampleNumerical rankRank-revealing QRSingular valuesCondition-estimationEckart–YoungHouseholder reflectionLow-rank approximationLower boundQR factorisationSpectral decay

All concepts