Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Column pivoting — where it appears

Choosing at each step the column with the largest remaining norm, which is greedy, usually right, and has nothing to choose between on Kahan's matrix. It is a greedy rule, it costs one norm update per step, and on Kahan's matrix every column has the same norm so it makes no choice at all.

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

1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision

Rank is a decision

A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap.

spectra · Rank κ(A) = 10⁶ throughout · κ(H) = 100 · the answer is the same answer for every basisorthonormal — κ(Z)1κ(ZᵀHZ)25.6relative error1.07·10⁻¹⁵first m basic — κ(Z)1.99·10⁸κ(ZᵀHZ)3.8·10¹⁶relative error0.0518pivoted basic — κ(Z)2.06κ(ZᵀHZ)31.9relative error6.71·10⁻¹⁶what the choice costsdensity, orthonormal1density, fundamental0.5κ(ZᵀHZ) ÷ κ(Z)², naive0.96error, pivoted choice6.7·10⁻¹⁶every one of them is a basisand one of them loses fourteen digits

The basis nobody chose on purpose

A method that eliminates a constraint has to pick a basis for its null space, and every basis is correct. Their condition numbers are eight orders apart, the reduced problem inherits the square, and the choice is usually made by a one-line rule nobody thought of as a numerical decision.

orthogonality · Null-space basis groundarcs of the treearcs off the treethe loop worst servedleast-resistanceκ(Z)11κ(ZᵀHZ)143κ, unit diagonal9.3nonzeros in Z426longest loop, arcs26worst path ÷ own arc0.97every tree gives a basis of whole numbersthe resistances decide which one to want

The tree the resistances choose

On a network every basic set is a spanning tree and every null-space basis is a set of loops with entries 0 and ±1, so no tree can make Z badly conditioned. The tree with the best-conditioned Z still gives loop equations 4.8 times worse than the tree of least resistance: the basis has to be chosen against the Hessian, and pivoting finds it only when it pivots on the resistances too.

orthogonality · Null-space basis 81930415263110²10⁴10⁶10⁸10¹⁰10¹²size of the matrix|rₙₙ| ÷ σₘᵢₙthe 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ₖₖ|σₖone factorisation, two verdicts‖AP − QR‖/‖A‖10⁻¹⁵|rₙₙ|1.1·10⁻¹²σₘᵢₙ10·10⁻¹³column interchanges33|rₙₙ| is never below σₘᵢₙso 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ₖₖ| within a factor of six of the σₖ 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.

Condition numberNumerical rankRank-revealing QRSingular valuesCounterexampleKahan's matrixNull-spaceNull-space basisQR factorisationReduced hessianToleranceBasis

All concepts