Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Schur form — where it appears

The triangular matrix — block triangular, over the reals — that an orthogonal similarity reduces any matrix to. Its diagonal carries the eigenvalues, and the reduction is what a practical eigenvalue routine returns instead of a diagonalisation.

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

first · leading5.47·10⁻⁶first · trailing4.62·10⁻⁵second · leading4.27·10⁻⁵second · trailing2.23·10⁻⁴symmetric · leading5.47·10⁻⁶symmetric · trailing4.05·10⁻⁵all six are the same algebrabest route5.5·10⁻⁶worst route2.2·10⁻⁴spread across the six41condition of the linearisation8.3·10¹²the spectra agreeand the arithmetic does not

Six routes to one spectrum

Three linearisations of one quadratic, each reduced to a standard eigenvalue problem two ways. All six have exactly the same eigenvalues in exact arithmetic. On a well-scaled problem they differ by noise; on a badly scaled one by a factor of forty; and two of the six are the same matrix.

polynomial · Linearisation backward error 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.

Condition numberKronecker productMatrix equationBackward errorFlop countBack-substitutionCompanion formEigenvaluesFill-inKronecker sumLinearisationMatrix polynomial

All concepts