Symmetric indefinite — where it appears
Named by 11 essays across 4 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.
A factorisation with nothing to pivot for
Cholesky's growth factor is not bounded by one. It is equal to one, at every size and every condition number, and the two-line reason is why the algorithm needs no pivoting at all — not "usually gets away without it". Its only failure is the square root of a non-positive number, which is exactly the test for definiteness, and in floating point that test moves with the precision.
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.
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.
Where the multipliers go
Bunch–Kaufman bounds the growth in D and not the entries of L, and the warning attached to that is that everything which later uses the factors inherits the size of L. On a matrix built to make those entries 1.2 over ε, they reach 1.2·10¹⁰ while the solve's backward error stays at 1.6·10⁻¹⁶, |L||D||Lᵀ| stays at 6.7 times ‖A‖, and a step of refinement changes nothing. The large multipliers are where the rule has put the matrix's ill-conditioning. A direction of negative curvature read from those factors finds 7·10⁻¹⁶ of the curvature that is there; the bounded rule's finds 13%.
A curvature direction the factors cannot refine
A direction of negative curvature read from Bunch–Kaufman's factors held 7·10⁻¹⁶ of the curvature that was there, and the bounded rule's held 14 per cent. The prediction was that a few steps of inverse iteration with the same factors would recover it from either. One step leaves both under a thousandth, and two put both on positive curvature, at the eigenvalue nearest zero — because a solve amplifies the smallest eigenvalue in magnitude, not the most negative. What recovers the curvature is the matrix, not its factors: Lanczos from either direction reaches ninety-nine per cent in six to nine products at every coupling, and power iteration from Bunch–Kaufman's direction has not reached a tenth after sixty.
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.
The push a pivot needs belongs to the matrix
An indefinite factorisation's most negative pivot looks like an estimate of the most negative eigenvalue, and on one planted family Bunch–Kaufman's, pushed a tenth further, was a usable shift for inverse iteration. On thirty random symmetric matrices neither rule's pivot is: unpushed it is nearest the smallest eigenvalue on 12 and 5 of them, pushed a tenth on 13 and 9, and only a push of two serves 29. The push each matrix needs runs from 0.59 to 2.27 for Bunch–Kaufman — whose pivot is more negative than every eigenvalue on eight matrices and under half the smallest on others — and from 0.85 to 2.01 for the bounded rule. What does work needs no push at all: multiply the shift by a quarter until the factorisation of A − σI has no negative pivot, which Sylvester's law says is exactly when σ is below the spectrum. It lands every time, in a median of two or three factorisations.
A small pivot with a small neighbour
A fill-reducing plan computed from the pattern loses its saving as small pivots are scattered through a symmetric indefinite matrix, and redrawing it where the pivoting test refuses it wins the saving back. Gather the same small pivots into one region and the prediction was that the fixed plan would do worse, because a whole region's ranking is wrong at once. It does better. On 8 × 8 and 10 × 10 grids the fixed plan is refused 0 to 6 times with the small pivots clustered, against 7 to 19 scattered, and at three in ten it saves 10 and 23 per cent of the natural order's factor where scattered it saved 3 and 9. The reason is in the Bunch–Kaufman test: a small pivot whose neighbour is also small cannot be passed over for that neighbour, so the test pairs the two into a block that keeps the planned row. Both plans still save something with half the diagonal small. And the step-by-step sparsest rule, best of all when the small pivots are scattered, falls behind the redrawn plan in a cluster.
A refusal has no fixed price
A symmetric indefinite factorisation planned once from the pattern is refused by its pivoting test where small diagonal entries sit, and the earlier essays read the refusal count as the plan's cost: scattered small pivots were refused 7 to 19 times and saved little, clustered ones 0 to 6 and saved much more. Put the small pivots along lines, each with two small neighbours, and the prediction of one refusal for every three small entries holds — between 0.25 and 0.42 on every share and grid. The rest of the reading does not. From a fifth of the diagonal up, the three layouts add within a factor of 1.6 of the same number of entries to the fixed plan's factor while their refusal counts differ by three to seven times. What moved the earlier savings was the baseline: the natural order's factor changes with the layout too, by 13 per cent at three in ten, and on the 10 × 10 grid the lines 'save' 19 per cent where the scatter saves 9 — with fixed-plan factors of 907 and 898 entries.
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.
Bunch–KaufmanGrowth factorLDLᵀ factorisationSaddle-point systemsFill-inInertiaMinimum degreeSparse pivotingSymbolic factorisationCholeskyRook pivotingCondition number