Saddle-point systems — where it appears
Named by 38 essays across 10 fields — each of them below, with the objects they name alongside 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.
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.
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.
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.
A condition number sent to infinity
An interior-point method manufactures an ill-conditioned matrix on every iteration, deliberately, because the separating of a diagonal is how it discovers which constraints are active. Written one way the answer keeps fifteen digits at a condition number of 3·10¹⁵. Written the other way — the way almost every code writes it — it has none left.
The regularisation that legalises every order
Perturb a saddle-point matrix's two blocks in opposite directions and it acquires a factorisation with a diagonal D under every symmetric permutation — not under a good one, under all of them. Five hundred random orderings, five hundred successes, and a growth factor that spans six orders across them.
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.
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.
A constraint is a weight at infinity
Stack an equality constraint on top of a least-squares problem with a large weight and the answer approaches the constrained one like 1/τ². The limit is takeable to any accuracy — and how far it can be taken is a property of the solver, not of the problem. One of them stops at the square root of the precision, and one of them does not stop.
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).
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.
What survives one step of the barrier
An interior-point method solves the same system dozens of times with the same pattern and different numbers, and exactly p entries change between one step and the next. The pattern is reusable for ever. The factorisation is reusable for none of them, and the threshold that says so is a reduction factor of about a per cent against schedules that use ten.
The half of a problem a sketch may touch
A sketch guarantees that a norm is preserved to within a factor. An equality constraint is a statement that a quantity is zero, and no multiplicative guarantee says anything about zero. Sketch a constrained problem written as a weighted one and the constraint is not destroyed — it is demoted, from a violation of 1/τ² to one of ε/τ, exactly half the exponent.
The active set before the digits
An interior-point method takes fifteen iterations on a quadratic programme with forty constraints, and its iterate has eight correct digits at the eleventh. Take the constraints its diagonal calls active at the first iterate, solve the equality problem they define once, and check the answer against the conditions for optimality. It passes, to thirteen digits. The step's matrix had a condition number of 43 at that iterate, and 7·10¹⁵ at the last.
An ordering that does not wait for the numbers
A sparse factorisation's memory is decided by an ordering computed from the graph, and its stability by pivots computed from the values, and the two decisions fight. On one family of matrices they do not — the ordering can be chosen for fill alone, and the fill the symbolic phase predicts is the fill the factorisation produces — exactly, not as a bound.
Where the augmentation puts the cost
Add γAᵀA to the objective block of a saddle-point system and its Schur complement tends to I/γ, so the cheapest possible approximation becomes the right one and the golden-ratio spectrum arrives — within 7.6·10⁻⁶ at γ = 10⁶. MINRES falls from 21 steps to 6. The inner solve with the augmented block rises from 14 conjugate gradient steps to 43, their product does not fall at all, and the answer loses seven and a half digits on the way.
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.
The perturbation that does the work
A saddle-point matrix made quasi-definite is perturbed in both blocks, and the laws measured for it moved both together. Moved apart, the laws all belong to one block. The zero block's perturbation γ decides whether every ordering factorises, sets the worst ordering's growth at 0.51/γ, and costs the answer 1,451 per unit — the reciprocal of the smallest eigenvalue of AH⁻¹Aᵀ to three figures. The perturbation of H moves none of the first two and costs 19 per unit. Refinement removes each block's perturbation at the rate its own Schur complement sets, so γ's limit sits fifty times nearer than δ's.
Two condition numbers of one matrix
κ₂ is a worst case over perturbations of a given norm, and a normwise perturbation may put its whole budget on the smallest entry. The componentwise number is a worst case over perturbations proportional to the entries, which is what a backward-stable factorisation actually makes. On one matrix they are 3·10¹³ and 13.3, and the error obeys the second.
Feasible and wrong
A third constraint that nearly repeats the first takes the best route's answer from 2.96·10⁻¹⁵ to 1.16·10⁻⁴, and the other two routes to no correct digit at all. Every one of those answers satisfies every constraint to 10⁻¹⁵. The quantity a caller checks after a constrained solve is the one quantity here that says nothing.
The condition number that does not know
Two constrained fits with the same size, the same number of constraints and the same κ(A) to twelve figures. One returns 4.7·10⁻¹⁶ and the other 3.0·10⁻⁴. What separates them is the conditioning of A restricted to the constraint's null space — 1.00 against 10¹² — which every solver computes on the way and none reports.
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.
The reference was a method
The optimality conditions of a constrained fit contain AᵀA, so solving them is the road that squares the problem wearing a block structure. At κ(A) = 10¹¹ the route that never forms a cross-product returns 1.89·10⁻⁹ and the route that does returns 4.64·10⁻⁴ — and forming AᵀA and then solving it in exact rationals returns 3.45·10⁻⁴, so nearly all of the loss happens before any elimination begins.
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.
A constraint the count stops seeing
Let one constraint drift towards being a combination of the others and the inertia of the saddle-point matrix keeps its promise only while σ²/|h| can be resolved — σ the constraint's smallest singular value, h the curvature along the direction it barely constrains. At h = −1 the count stops seeing the constraint at σ = 1.4·10⁻⁹, six decades before any rank test would drop it, and below that it reports a genuine minimum as a saddle on three to six draws in eight. No shift of H brings the constraint back: the correction loop shifts a problem that needed nothing by as much as 2,620. A perturbation of the constraint block does not bring it back either — it decides, at σ = √(|h|δ).
The freedom a symmetric factorisation does not have
Permuting rows and columns together leaves no column to choose, so the conflict between the sparsest pivot and the sound one should be worse rather than better. On a saddle-point matrix whose constraint rows have no diagonal entry at all, it is not there: taking the sparsest available pivot holds 70 entries against the natural order's 113 and a growth of 1.28 against 1.83 — better on both currencies at once, at every setting of the pivot test. The two-by-two blocks that make it legal cost 1.33 entries apiece.
A loop that asks the null space why
An inertia-correction loop sees only an integer, and two different faults produce the same wrong one: curvature that needs a shift, and a constraint too weak for the count to see. One QR of the constraint matrix on a wrong count tells them apart — it shifts none of the 22 weak-constraint minima the ordinary loop shifted by up to 2,621 — and its reduced eigenvalue gives the shift a saddle needs in one step, twice the need exactly, where the schedule overshoots by up to 17,783 times. But at κ(A) = 10⁸ the loop still certifies 57 saddles of 152, because a false certificate is a count that read right, and a check made only on wrong counts never sees it. Asking every time leaves five, all shallower than 2·10⁻⁸.
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.
A multiplier is a force
A third constraint nearly parallel to the first made the multipliers of a constrained fit rise in exact proportion to κ(B), which looked like the conditioning measured a second, dearer way. It was not. Give the third constraint a datum that asks for nothing new and, at the same κ(B) = 4.6·10¹², the multipliers are eighteen thousand times smaller; give it a strain δ and they are 0.0133 δ/ε², a force on a lever of length ε. What they measure is what the constraint asks. What they do not measure is the error of the best route, which sits at the same level whether the constraint asks for nothing or for a displacement of 3·10⁹.
An augmentation read in the smallest eigenvalue
An augmented Lagrangian preconditioner's least work sat at γ = 1, 10⁴ and 1 on three systems, and two of the three optima sat where the smallest generalised eigenvalue was about 0.06 — which suggested a rule written in ν rather than γ. On twenty-four systems whose norms are all one, the least-work γ spans seven decades and ν at the optimum spans a factor of thirty, so there is no one ν. There is still a rule: take the smallest γ at which ν reaches 0.03, and the median system pays 7 per cent over its least work and the worst 29, where the best single γ pays 61. Its price is digits — twelve times the best forward error on the median system, 4,561 times on the worst.
An order fixed before the numbers
On a saddle-point matrix whose constraint rows have no diagonal, taking the sparsest pivot at every step beat the natural order on fill and growth at once, and the reading was deferral: the constraint rows go last and have filled in by then. A code computes its ordering once, from the pattern. That static minimum-degree order holds fewer entries than re-reading the degrees on fourteen of sixteen settings, growth under two throughout — and it does not defer. It spreads the constraint rows through the elimination, each after two thirds of its own variables. Scatter small pivots through a grid instead and the plan is refused on up to 25 of 64 steps; its saving falls from 31 per cent to 3.
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.
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.
The scale that only moved a pivot
Multiply the constraint rows of a saddle-point system until its multipliers are the size of its solution, and the extra error the route was blamed for — 4.6·10⁻⁴ against the null-space route's 1.8·10⁻⁸ — falls to 3.3·10⁻⁸. The prediction holds and its reason does not. A scale of ten does what a scale of 6·10⁵ does; hold the elimination's row order fixed and nine decades of scale move the error by less than a factor of five. What the scale changed was which row partial pivoting took at the second step, and taking the constraint rows first does the same job with no scale at all.
A plan redrawn where it was refused
A symmetric indefinite factorisation planned once from the pattern loses its fill saving as small pivots are scattered through the diagonal — on an 8 × 8 grid it keeps 74 per cent of what re-reading the degrees at every step saves at one small pivot in twenty, and 20 per cent at three in ten. Redraw the plan for the remaining rows only when the pivoting criterion rejects the planned pivot, and it keeps 85 to 100 per cent at every share up to three in ten, reading a tenth to a quarter of the rows the step-by-step rule reads. Each redrawn plan heads off refusals that would have followed it: 3 re-plans where the fixed plan was refused 7 times, 9 where it was refused 17. Where the plan was never refused, redrawing costs nothing — and with half the diagonal small, no plan of any kind beats the natural order.
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.
The switch is read before the solve
Scaling the constraint rows of a saddle-point system rescued the route to a constrained least-squares fit by changing which row partial pivoting takes at the second step. The scale at which it changes can be read before anything is solved: scaling multiplies every constraint row's candidate by s and leaves every other row's alone, so one unscaled elimination, recording the two kinds of candidate at each step, gives the switch exactly — on all forty-nine problems, to within one part in 10¹⁵ of what bisection finds, decided at the second step everywhere but at a coupling of one. A scale just past it removes the catastrophe where there was one. It does not make the route as good as eliminating the constraints first: on four problems every scale tried is thirty to thirty-nine times worse, and they are the problems where the unscaled route was too.
An eigenvalue count that cannot be slightly wrong
Every spectral computation here returns floats with errors in them. Counting eigenvalues below a shift by the signs of an unpivoted elimination returns an integer, and an integer cannot be 6.9999999997 — so the answer is exactly right, or wrong by a whole eigenvalue, and where the second happens is a band of measurable width.
Named alongside it
The objects these essays reach for when they reach for this one.
Condition numberExact ground truthReduced hessianInertiaLDLᵀ factorisationSchur complementCertificateIndefinite matrixConstrained minimisationEquality-constrained least-squaresQuasi-definite matrixForward error