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.

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

Also named here as numerical rank, rank-revealing qr — the same set of essays touches all of them, so they are one junction rather than several.

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 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.

Numerical rankRank-revealing QRSingular valuesCondition estimationCondition numberCounterexampleHouseholder reflectionJacobi's eigenvalue methodKahan's matrixLower boundQR factorisationRank deficiency

All concepts