Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Matrix exponential — where it appears

The solution operator of ẋ = Ax, computed by scaling a matrix down, approximating, and squaring the result back. Scaling and squaring is what a library runs, and the squaring back is where the accuracy is decided rather than in the approximation.

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

Also named here as matrix function — the same set of essays touches all of them, so they are one junction rather than several.

10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁴10⁻¹10¹²10²⁵10³⁸10⁵¹10⁶⁴δ, the gap between consecutive eigenvaluesrelative error in eᴬan answer with no correct digitsV f(Λ) V⁻¹scaling and squaring‖A(δ) − A₀‖exact eigenvalues throughoutκ(V) at the smallest δ3.3·10⁸²eigen route2.9·10⁶⁵scaling and squaring4.1·10⁻¹²distance to the limit7·10⁻¹²the eigenvalues are the diagonaland they are exact at every stop

A function of a matrix is not a function of its entries

Everybody learns that f(A) means diagonalise, apply f to the eigenvalues, undiagonalise. That is a definition, not a method. On a matrix seven picometres from a defective one — with exact eigenvalues and eigenvectors from a closed form — the definition returns an answer wrong by sixty-five orders of magnitude, and a method that never mentions an eigenvalue returns the right one.

spectra · Matrix function 10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁴10⁻¹10¹²10²⁵10³⁸10⁵¹10⁶⁴δ, the gap between consecutive eigenvaluesrelative error in eᴬan answer with no correct digitsV f(Λ) V⁻¹scaling and squaring‖A(δ) − A₀‖exact eigenvalues throughoutκ(V) at the smallest δ3.3·10⁸²eigen route2.9·10⁶⁵scaling and squaring4.1·10⁻¹²distance to the limit7·10⁻¹²the eigenvalues are the diagonaland they are exact at every stop

The series that has to be squared back

The Taylor series for the matrix exponential is not wrong — every term is computed correctly — and on Moler and Van Loan's two-by-two its largest term is 5.4 million times the answer it sums to. The method that replaces it scales the matrix down and squares the result back, and both halves of that sentence cost: too few squarings and the approximant is out of range, too many and each one doubles the rounding.

spectra · Matrix function 0481216202410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹matrix–vector products, mrelative error in eᴬbforming e^A: 3·10⁻¹⁶crosses at m = 18the vector, not the matrixsteps to the dense answer18dimension100Krylov megaflops0.36dense megaflops2the exponential that is computedis 18×18

The vector was what was wanted

Nobody who computes a matrix exponential wants the matrix. They want eᴬᵗb — one vector, the state of a system at a later time. Twenty matrix–vector products get it to sixteen digits on a hundred-by-hundred problem, without ever forming a hundred-by-hundred exponential, and the exponential that does get computed is twenty by twenty.

spectra · Matrix function 01020304050607010⁻⁶10⁻³110³10⁶10⁹k‖Aᵏ/k!‖‖e^A‖ = 2.6largest term 1.4·10⁷what the series throws awaylargest term1.4·10⁷‖e^A‖2.6digits cancelled away5.4·10⁶error after the sum5.2·10⁻⁹every term is computed correctlyand the sum has lost seven digits

The error the method already knows

Summing the exponential's Taylor series throws away a known number of digits, and the number is on the machine while the sum is being formed. The largest term divided by the answer, times the unit roundoff, tracks the relative error that comes out — to within a factor of nine, across fourteen orders of magnitude of it — and nothing reports it.

spectra · Matrix function

Named alongside it

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

Exact ground truthMatrix functionCancellationFlop countNon-normalityArnoldiCatastrophic cancellationCondition-estimationCondition numberDefective matrixEigenvaluesEigenvectors

All concepts