Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Minimal polynomial — where it appears

The monic polynomial of least degree that a square matrix satisfies. Its degree is the number of steps after which a Krylov method terminates exactly, so it counts the distinct eigenvalues and adds one for each extra step a Jordan block demands.

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

00.3670080.7340171.101031.468031.835040eigenvalue of P⁻¹Kwritten down, then computeddistinct3at 16φ computed1.6off the closed form2.9·10⁻¹⁴1 − φ1φthe preconditioner's effect is a theoremand the golden ratio is in it

Three eigenvalues, and two are the golden ratio

Precondition a saddle-point system by the block diagonal of its own two definite pieces and the preconditioned matrix has exactly three distinct eigenvalues — 1, and the two roots of λ² − λ − 1. A minimal polynomial of degree three means three steps, at every conditioning, and the preconditioner nobody can afford turns out to be the statement the affordable ones are measured against.

constraint · Block preconditioning -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

Named alongside it

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

Block preconditionerKrylov subspaceMINRESPreconditioningSaddle-point systemsSchur complementDefective matrixExact ground truthGMRESGolden ratioIndefinite matrixJordan form

All concepts