Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Matrix equation — where it appears

An equation whose unknown is a matrix rather than a vector, such as AX + XB = C. Writing it as an ordinary linear system squares the dimension, so it is solved through factorisations of its coefficients instead.

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

123456710⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹order r kepterror and bounds2Σσ, and the errorσᵣ₊₁a bound that is an equalityorders7bound ÷ error, worst1spread over the sweep1error ÷ σᵣ₊₁, worst2.1computed before the modeland attained by it

The bound that is known in advance

Almost every error in numerical linear algebra is measured after the fact. Balanced truncation has one that is computable before the reduced model exists, in a norm of a function rather than of a residual — and on ordinary problems it is not an upper bound that is loose. It is attained.

reduction · Balanced truncation 01234567810⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹μ, the entry above the diagonalsep, and the eigenvalue gapmin |λᵢ + μⱼ|sep(A, B)the spectra never moveeigenvalue gap, throughout2sep at μ = 02sep at μ = 89.5·10⁻⁴amplification there1056solvability is the eigenvaluesand conditioning is not

An equation whose unknown is a matrix

AX + XB = C is linear in X, so it has a coefficient matrix, and writing it down is the obvious thing to do. At n = 100 that matrix has a hundred million entries for a problem with ten thousand unknowns, and the algorithm everybody uses instead never forms it. Its conditioning is not the eigenvalue gap either, which is the number a reader is invited to consult.

structure · Matrix equation A6×6B6×6I ⊗ A + Bᵀ ⊗ I36×36one equation, two objectsentries in A and B72entries in the coefficient matrix1296two routes, relative gap1.7·10⁻¹⁶‖AX + XB − C‖/‖C‖1.4·10⁻¹⁶the small squares are the problemand the large one is the notation

The elimination the matrix does not need

The Kronecker form of AX + XB = C is dismissed with a hundred million entries and (2/3)n⁶ operations. Both price an elimination, and after the reduction both routes take, the matrix has exactly n³ nonzeros, none of them above the block diagonal, and nothing left to eliminate.

structure · Matrix equation backward error ÷ residualC = 0.5 X, κ(X) 10⁸5.5C = 10⁻² X, κ(X) 10⁸185C = 10⁻⁴ X, κ(X) 10⁸9306C = 10⁻⁶ X, κ(X) 10⁸2.1·10⁵110¹10²10³10⁴10⁵10⁶10⁷κ(X), on a logarithmic scalebackward error ÷ residual10⁰10²10⁴10⁶10⁸C = 0.5 XC = 10⁻² XC = 10⁻⁴ XC = 10⁻⁶ Xdashed: 2√2 μ, the boundthe residual is not the backward error

A backward error the answer does not feel

Both ways of solving AX + XB = C leave a residual at the rounding level, and for a linear system that would be backward stability. For the equation it is not: the smallest perturbation of A, B and C that makes the computed X exact can be far larger. On a family built to make it so — X increasingly ill conditioned, C increasingly small beside AX — the structured backward error of Bartels and Stewart's solution climbs to 2.1·10⁵ times its residual, and the Kronecker system's, whose residual is four times smaller, to 2.0·10⁶, within the bound Higham's μ sets. And the error of the answer does not move. Against the exact X it stays where the size of C puts it, 6·10⁻¹⁵ to 1·10⁻⁹, across eight decades of κ(X). The perturbation that makes the backward error large has to sit on C, along directions X is insensitive to, and so the backward error rises and the answer never feels it.

structure · Matrix equation

Named alongside it

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

Kronecker productSchur formCondition numberFlop countA-priori boundBack-substitutionBackward errorBalanced truncationEigenvaluesExact ground truthFill-inGramian

All concepts