Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Relative accuracy — where it appears

Accuracy measured against a value's own size rather than against the largest one, which is what a small singular value needs and rarely gets. It is what a small singular value needs and what a general algorithm does not deliver, and it is achievable on matrices whose grading a diagonal factor absorbs.

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

-5-3.20611-1.412210.3816782.175573.969460log₁₀ |λ||λ| = 1λλ′ = 1, in the algebrapairs6decades of spectrum9.6pairing error, general3.3·10⁻⁹pairing error, structured2.2·10⁻¹⁶a symmetry the solver never knew aboutand the half of the answer it decides

A spectrum that comes in reciprocal pairs

A palindromic quadratic reads the same backwards, so λ is an eigenvalue exactly when 1/λ is. A general solver discards that, computes the large half of the spectrum perfectly and the small half to seven digits — and the small half is a division away from being perfect too.

polynomial · structured spectrum 1234567810⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹singular value, largest firstrelative errorone-sided Jacobizero-shift QRshifted QReigenvalues of BᵀBagainst a rational bisectionσ_min, exactly2.1·10⁻³⁰worst, one-sided Jacobi4.4·10⁻¹⁶worst, zero-shift QR2.2·10⁻¹⁶worst, eigenvalues of BᵀB1a relative error is a ratioand the denominator is the answer

Small compared to what

This site's own singular value routine has carried a sentence since the month it was written — that one-sided Jacobi computes the small singular values to high relative accuracy and the standard method does not. It has never been measured here, because measuring it needs a σ that is known rather than computed. A bidiagonal matrix and a Sturm count in exact rationals supply one.

spectra · relative accuracy 1234567810⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹singular value, largest firstrelative errorone-sided Jacobizero-shift QRshifted QReigenvalues of BᵀBthe same four routes, reversedσ_min, exactly5.2·10⁻²⁶Jacobi's error on it0.015sweeps, zero shift400sweeps, shifted16a method is not accuratea method on a matrix is

Accurate is not a property of a method

A bidiagonal matrix whose every entry is 1 or 4096 has singular values spanning thirty decades. On it, the method recommended for small singular values loses the small one by one and a half per cent, the sweep with the theorem behind it does not converge at all, and the shift the theorem is a warning about gets every value to 5·10⁻¹⁶. Nothing there contradicts the theory.

spectra · relative accuracy

Named alongside it

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

Bidiagonal matrixExact arithmeticGraded matrixJacobi's eigenvalue methodSingular valuesCancellationCayley transformCondition numberCondition squaringConvergence rateEquilibrationGeneralised eigenvalue problem

All concepts