Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Numerical rank — where it appears

The number of singular values above a threshold, which is a decision rather than a property and is answered differently by the two routines that estimate it.

Named by 4 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 significand bits10³10⁴10⁵10⁶10⁷10⁸10⁹10¹⁰κ(A)87892634456329625911109435761199127514162024every matrix positive definiteruns producing a false certificate14of runs in total72never above, in significand bits12first κ at eight bits10⁵the comparison was correctand what it proved was not true

Deciding that a zero has arrived

The previous tolerances were offers — accept this much error, save this much work. A detection threshold is not an offer, because both directions are failures. One matrix here has three genuinely near-invariant subspaces, and the constant somebody typed decides which of them the recurrence stops at; at eight significand bits the same kind of constant produces a proof of something false.

error · deliberate zero 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 λ = 0λ = ∞λ = ∞-0.37690.5654.3836.4282 eigenvalues here, and it is one placecounted exactly, in rationalsfinite eigenvalues4at infinity2degree of det(A − λB)4worst residual, either kind5.5·10⁻¹⁴an eigenvalue is a ratioand a ratio has a direction, not a size

An eigenvalue with no value

If the second matrix of a pencil is singular then some of the eigenvalues are infinite, and that is not a degeneracy — it is the algebraic constraints of the model, one per constraint. What survives is a pair of numbers rather than one, and on the line those pairs live on, infinity is an ordinary point with an ordinary residual.

spectra · pencil

Named alongside it

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

Singular valuesColumn pivotingCounterexampleInfinite eigenvalueRank-revealing QRToleranceBackward errorCertificateCondition estimationCondition numberDescriptor systemDeterminant

All concepts