Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Indefinite matrix — where it appears

A symmetric matrix with eigenvalues of both signs, which has no Cholesky factor and no minimum for a quadratic to have. It has no Cholesky factor, so the elimination that detects that is also the definiteness test, and a quadratic on it has a saddle rather than a minimum.

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

-1-0.582271-0.1645420.2531860.6709151.088641.506370eigenvalue4 negative10 positivecounted before it was formedpositive10negative4at zero0innermost ratio39the zero block is a theoremand so is the count either side of it

The zero that is not a missing entry

A constrained minimisation produces a matrix with a zero block, and the zero is a theorem rather than a sparsity pattern. No pivot order makes it positive definite, no precision changes that, and Cholesky does not fail somewhere on it — it fails at the first constraint row, on a number the problem already contained.

constraint · Saddle-point systems 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 D from PAPᵀ = LDLᵀ — the shaded pairs are 2×2 pivots10⁻⁶0.749······0.749·········1.2·10⁻⁶1.4······1.4·········2.1·10⁻⁶0.549······0.549·········3.6·10⁻⁶0.614······0.614·three rules, one matrix‖PAPᵀ − LDLᵀ‖, blocks5.8·10⁻¹⁷‖PAPᵀ − LDLᵀ‖, diagonal3.1·10⁻¹¹growth, blocks1.3growth, diagonal5·10⁵the zero block is what the problem saysand one rule does not need it to be nonzero

When symmetry is not enough

The matrix [[0, 1], [1, 0]] is symmetric, nonsingular and perfectly conditioned, and there is no diagonal entry to pivot on. Every factorisation restricted to symmetric interchanges and one-by-one pivots fails on it, at any depth of searching, because every entry it could search is zero. The repair is to take two variables at once.

elimination · Cholesky -5-3-11350eigenvalueHZᵀHZK4 negative — Cholesky of H stops at row 30 negative — a minimum on the constraint(10, 4, 0) = In(ZᵀHZ) + (4, 4, 0)one factorisation, no Zpositive, LDLᵀ of K10negative, LDLᵀ of K4negative in H4negative in ZᵀHZ0the count follows the reduced Hessiannot the Hessian

A minimum the Hessian cannot see

A Hessian with four negative eigenvalues can sit at a constrained minimum, and a Cholesky of it stops at the third row. One symmetric indefinite factorisation of the saddle-point matrix settles the question anyway — ten positive pivots and four negative — without a basis for the null space ever being formed. The count is exact in the algebra and blind in floating point, in a band that grows like κ(A)²; the route through the null space is blind in one that grows like κ(A).

constraint · Saddle-point systems 01234567910δ added to Hpositive pivots−λmin(H) = 4.67|μ| = 1minimumsaddlewhat the signs are countingminimum, true count10saddle, true count9saddle read as minimum from1.1guarantee needs δ past5.1the signs count ZᵀHZ + δInot the curvature the problem has

A shift that certifies a saddle

On a constrained problem whose Hessian has four negative eigenvalues, a saddle-point matrix is quasi-definite only once H + δI is positive definite — past δ = 5.08 here. Its pivot signs then count the curvature of ZᵀHZ + δI rather than of ZᵀHZ, so a saddle with a negative curvature of −1 is certified a minimum from δ = 1.05 on, and every saddle shallower than δ goes the same way. Iterative refinement against the unregularised matrix keeps the second-order test the count gave up: it contracts on the minimum at δ/(μ + δ), 0.980 a step at δ = 5, and on the saddle it grows at exactly 1.25.

constraint · Quasi-definite 10⁻³10⁻²10⁻¹110¹10²10³10⁴10⁵the shift the reduced Hessian neededshift taken ÷ shift needed10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹median of eightexactly enoughκ(A) = 10, eight draws per curvatureworst ratio, curvature 10⁻⁸·²⁵1.8·10⁴worst ratio above 10⁻²7.3trials stopped below the curvature0factorisations a solve, mean3.2above one: more convex than the problemon the floor: the count passed a saddle

The shift that stops at the first right count

A nonconvex solver that finds the wrong inertia adds δI to H and tries again, and the δ it settles on is used as though it measured the curvature it corrects. It does not. On a well-conditioned constraint it is the schedule's number — 1.8·10⁴ times the need at a curvature of 5.6·10⁻⁹, between one and 7.3 times above 10⁻² — and on an ill-conditioned one the loop stops wherever the count first reads right: 63 of 152 saddles at κ(A) = 10⁸, the deepest with curvature 56. Refining the shift by bisection removes the first error and adds to the second.

constraint · Saddle-point systems μ = −0.01, δ = 7saddle's growth a step0.0014minimum's fall a step0.014residual verdict, step6205010015020010⁻¹10¹refinement steprelative residual, relative errorsaddle, residualsaddle, errorminimum, residualminimum, errorthe pivot signs call both of these a minimumthe residual does not

The residual turns before the error doubles

Regularise a saddle-point matrix past the Hessian's most negative eigenvalue and its pivot signs certify every shallow saddle as a minimum; refinement against the unregularised matrix keeps the test, as a rate, and a saddle at a hundredth of the regularisation grows by only 1.0014 a step — 485 steps to double. That was read as hundreds of steps before the history says anything. The residual, which is what a solver actually has, says it at step 62: a fit of its logarithm over the last ten steps turns positive there and stays positive, while the minimum's is negative from step 10. Across five regularisations the verdict comes at an eighth of the doubling time.

constraint · Quasi-definite rounding finds every hidden saddleμ = −0.01: share zero, verdict at step2723μ = −0.1: share zero, verdict at step1102μ = −1: share zero, verdict at step18110¹10²10³decades of the growing direction removed from the right-hand sidestep the verdict settles0246810121416allμ = −0.01μ = −0.1μ = −1dashed: the growth against the slowest contractiona decade of hiding is a fixed number of steps

The right-hand side that hides the saddle

Refinement against an unregularised saddle-point matrix gives the second-order verdict the pivot signs cannot, from step 62 on the shallowest saddle — for one right-hand side. The verdict depends on how much of the growing direction the right-hand side contains, and it can contain none. Each decade removed delays the verdict by a fixed number of steps, 147 on the shallowest saddle, set by the growth against the minimum's slowest contraction rather than by the growth alone, which predicted 1,611. Rounding stops the hiding at about 2,700 steps — but by then refinement has solved the system to a residual of 2.6 times ten to the minus thirteen, and any stopping test has already accepted it. A random kick to the starting point costs nothing and finds it.

constraint · Quasi-definite μ = −0.1 and −0.01both hidden: steps a decade81the faster direction's race81the slower direction's race14710¹10²10³decades of the hidden directions removedstep the verdict settles0246810121416allboth directions hiddenonly the faster hiddenonly the slower hiddenμ = −0.1 aloneμ = −0.01 alonedashed: a single saddle of each curvatureone hyperplane hides nothing

One hyperplane hides nothing

Iterative refinement against a saddle-point matrix gives its verdict when the growing direction overtakes the minimum's slowest decay, and a right-hand side with that direction removed delays it by a fixed number of steps a decade. With two negative curvatures, the prediction was that hiding both is paid for by the faster, and that hiding only the faster leaves the slower one's race to run. The first half holds to half a per cent on three pairs, and to one and a half on two whose curvatures differ by a factor of two and of 1.2. The second does not: hiding either direction alone moves the verdict by a fixed handful of steps, the same at two decades as at sixteen, because the direction left in view is already growing. Only the intersection of the two hyperplanes hides anything — and it hides less than either curvature can alone, 1,127 steps at worst against 2,907, with random right-hand sides' slowest at 79 against 417.

constraint · Quasi-definite 012345678-7-5-3-11357conjugate gradient steppᵀAp ⁄ pᵀpλₘᵢₙ = -0.1positive: a step existsnegative: a certificate existsone matrix, two questionsstep it turns at6quotient there-0.027share of λₘᵢₙ recovered0.27λₘᵢₙ, by construction-0.1MINRES steps on the same system37the division that cannot be doneis the answer to a different question

The division that cannot be done

Conjugate gradients divides by pᵀAp at every step, and on a matrix that is not positive definite that number can be zero or negative. The guard against it has been here from the first essay and described it as a failure. In the method that made conjugate gradients famous it is the single most valuable object the iteration can produce, and it costs six matrix–vector products.

iterative · Breakdown 10⁻³10⁻²10⁻¹1024681012size of the negative eigenvalue, −λproducts before the test firesharder to find, and milder8 spectra, n = 50products at the largest λ3products at the smallest10smallest share of λ recovered0.14largest0.34the one that hidesis the one that matters least

A proof that does not ask how large the matrix is

Proving a Hessian indefinite costs three matrix–vector products when the negative eigenvalue is 3 and nine to eleven when it is a thousandth, and that pair of numbers barely moves across a fourfold range in n. The factorisation that settles the same question costs a third of n³, which grows by a factor of sixty-four over the same range.

iterative · Breakdown 110¹00.30.60.91.2trust-region radius Δshare of the exact model decreasethe exact subproblem7 radii, n = 60share at the smallest radius0.95share at the largest0.3products, at most8radii stopped by the curvature4a few products against an eigendecompositionand most of the decrease

The certificate that arrives soonest is worth least

The more negative a Hessian's smallest eigenvalue, the sooner conjugate gradients meets a direction of negative curvature — and the less of the exact trust-region decrease that direction turns out to be worth. At λₘᵢₙ = −10 the step arrives after two products and gets 39.6 per cent; at −10⁻³ the same two products get 89.8, and the whole sweep costs eight.

iterative · Trust-region

Named alongside it

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

CertificateSaddle-point systemsInertiaReduced hessianConstrained minimisationCholeskyIterative refinementKrylov subspaceLDLᵀ factorisationNegative curvatureQuasi-definite matrixBunch–Kaufman

All concepts