Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Constrained minimisation — where it appears

Minimising subject to equations, whose stationarity conditions are a saddle-point system in the variables and their Lagrange multipliers. Its stationarity conditions produce a saddle-point system, which is where a zero on the diagonal arrives from the model rather than from bad luck.

Named by 8 essays across 4 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 01234510⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹log₁₀ κ(A)condition number, and relative errorκ(S)κ(ZᵀHZ)range-space errornull-space erroragainst a BigInt answerκ(S) at κ(A) = 10⁵4·10¹⁰κ(ZᵀHZ), all stops21range-space forward error5.3·10⁻⁶null-space forward error5.8·10⁻¹²both are the same algebraand only one squares

Two ways to remove a constraint

A constrained system can be reduced by eliminating the multipliers or by eliminating the constrained directions. Both give the same answer in exact arithmetic and inherit different condition numbers — one of them squares the constraint's, and the other does not contain it at all.

constraint · Saddle-point systems 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 κ(A) = 10⁶ throughout · κ(H) = 100 · the answer is the same answer for every basisorthonormal — κ(Z)1κ(ZᵀHZ)25.6relative error1.07·10⁻¹⁵first m basic — κ(Z)1.99·10⁸κ(ZᵀHZ)3.8·10¹⁶relative error0.0518pivoted basic — κ(Z)2.06κ(ZᵀHZ)31.9relative error6.71·10⁻¹⁶what the choice costsdensity, orthonormal1density, fundamental0.5κ(ZᵀHZ) ÷ κ(Z)², naive0.96error, pivoted choice6.7·10⁻¹⁶every one of them is a basisand one of them loses fourteen digits

The basis nobody chose on purpose

A method that eliminates a constraint has to pick a basis for its null space, and every basis is correct. Their condition numbers are eight orders apart, the reduced problem inherits the square, and the choice is usually made by a one-line rule nobody thought of as a numerical decision.

orthogonality · Null-space basis -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 081624324000.250.50.7511.25angle of the strong direction (degrees)ratio, and convergence factorenergy ratio of oneenergy ratioclassicalminimiserwith the constraintwhere the formula is optimalenergy ratio at 0°1energy ratio at 45°1.2classical rate at 45°0.35the minimiser's rate there0.28a ratio of exactly one while the assumption holdsand a diagnostic when it stops

The formula that was already optimal

Ask for the interpolation that minimises the energy of its own columns and the answer is the classical AMG formula — to zero at every row of the one-dimensional Laplacian, and to four digits in two dimensions. On the operator rotated to 45° the two part company, and the gap between them is a diagnostic that needs no reference solution.

iterative · Algebraic multigrid 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

Named alongside it

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

Saddle-point systemsCondition numberIndefinite matrixReduced hessianInertiaLDLᵀ factorisationBunch–KaufmanCertificateSchur complementCholeskyNull-spaceNull-space method

All concepts