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 3 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 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.

Block preconditionerMINRESSaddle-point systemsSchur complementDefective matrixGMRESJordan formKrylov subspacePreconditioningExact ground truthGolden ratioIndefinite matrix

All concepts