Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Block preconditioner — where it appears

A preconditioner built from the blocks of a matrix rather than from its entries, usually by keeping some blocks exactly and discarding or approximating others. For a saddle-point system the two standard choices have spectra that are written down in closed form rather than measured.

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 012345610⁻³10⁻²10⁻¹110¹log₁₀ κ(A)eigenvalue of P⁻¹Kthe constraint is not in itnontrivial6at one8movement, six decades7.1·10⁻⁶drift at one6·10⁻⁵2m at onethe marks are a pencil that never saw Aand the lines are the preconditioned matrix

A preconditioner that need not know the constraint

Keep the constraint block exactly and replace the objective block by anything positive definite on the null space. The preconditioned matrix then has 2m eigenvalues at exactly one, and its remaining n − m are the generalised eigenvalues of a pencil in which the constraint does not appear. Sweep its condition number over six decades and they do not move in six digits.

constraint · block preconditioning

Named alongside it

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

MINRESPreconditioningSaddle-point systemsCondition numberConstraint preconditionerExact ground truthGolden ratioIndefinite matrixInertiaKrylov subspaceMatrix pencilMinimal polynomial

All concepts