Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Jordan form — where it appears

The form a square matrix reaches under similarity, with each eigenvalue carried by blocks that hold it on the diagonal and ones just above. A block larger than one marks a defective eigenvalue, whose computed value moves by a root of a perturbation rather than in proportion to it.

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

-1-0.500.511.50eigenvalue of P⁻¹Ktriangular [[H, Aᵀ], [0, −Ŝ]] — 1 valuediagonal blkdiag(H, Ŝ) — 3 valuessteps to a residual of 10⁻¹⁰GMRES, triangular2MINRES, diagonal3‖P⁻¹K − I‖54computed |λ − 1| at c = 18.1·10⁻⁸one copy of each value against twoand the counts follow

One eigenvalue and two steps

Put the off-diagonal block back into a block-diagonal saddle-point preconditioner and every eigenvalue of the preconditioned matrix becomes exactly one. GMRES still needs two steps, because the matrix is the identity plus a nilpotent part of norm 54, and a computed eigenvalue at one comes back as a ring of radius 8·10⁻⁸ — the square root of the rounding, not the rounding. With an approximate Schur complement the triangular form leaves one copy of each value where the diagonal form leaves two, and the step count halves.

constraint · Block preconditioning 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⁻⁶10⁻⁴10⁻²1inner accuracy τdistance from one, or residualJordan pairs: √τresidual, step 2: τthe rest: τdashed: slope ½ and slope 1 through the measurementsthe split is a square root, the residual is not

A square root the residual does not pay

With the exact Schur complement, the triangular saddle-point preconditioner puts every eigenvalue at one in Jordan blocks of size two, and GMRES finishes in two steps. Solve the first block only to a relative accuracy τ and the blocks split: their eigenvalues leave one like √τ — 0.42 to 0.62 times √τ on eighteen systems across six decades, each pair exactly where a five-by-five eigenproblem puts it — while the rest move like τ. The question left open was whether that square root reaches the iteration. It does not. GMRES's residual after two steps grows like τ, with a slope of 0.86 to 1.27 on every system, because its polynomial has a double root at one and cancels each split pair to second order; every further pair of steps divides the residual by about the same factor; and a rule written in τ alone predicts the step count exactly on 179 of 234 runs and within one on 228.

constraint · Block preconditioning

Named alongside it

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

Defective matrixBlock preconditionerGMRESMinimal polynomialMINRESSaddle-point systemsSchur complementCondition numberEigenvaluesEigenvectorsExact ground truthInexact newton

All concepts