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.
The essay that opened this anchor is
about a fight. A sparse factorisation’s memory is decided by an ordering computed from the
graph, before any number is looked at; its stability is decided by pivots computed from the
values, during the factorisation; and the second can force the first to be wrong. The essay
after it measured the consequence: the
symbolic phase can only produce an upper bound, and the allocation has to be able to grow.
There is a family on which the fight does not happen, and the reason is one line of algebra
rather than a heuristic.
Fig. 1 Three orderings of one sparse saddle-point matrix, with the fill each produces. The two numbers
under each panel are a prediction and a count.
A quasi-definite matrix — symmetric, with a positive definite (1, 1) block and a negative
definite (2, 2) block — has an LDLᵀ factorisation with a diagonal D under every symmetric
permutation. The constraint field’s essay on
it has the proof and measures the claim
against five hundred random orderings.
The consequence for this field is immediate and it is the whole page. If a factorisation exists
in every order, the numeric phase has no reason ever to depart from the order the symbolic phase
chose. There is no pivot search, no threshold, no delayed pivot, no dynamic reallocation — the
numeric phase is a loop that fills in an array whose shape was fixed before it started.
So the ordering can be chosen for fill alone, which is what the fill-reducing heuristics were
designed to do and what nothing else lets them do without a numerical veto.
Fig. 2 With constraints touching five unknowns apiece, where there is more fill to reduce and the
orderings separate further.
A stiffness block of twenty-four unknowns with four constraints, each touching three consecutive
variables — a bordered band, which is what a finite-element problem with multipoint constraints
actually looks like. Three orderings, all computed from the sparsity pattern alone:
Predicted from the graph before any number is touched, and matched entry for entry by the
factorisation of the regularised matrix. Not bounded — matched.
That is the claim the anchor’s earlier essay could not make. There the symbolic count is an upper
bound and the numeric count comes in under it when cancellation makes a structurally nonzero
entry numerically zero, or over it when a pivot moves. Here the second cannot happen, and the
first is checked: the counts agree exactly, so no cancellation occurred either.
Fig. 3 The same comparison in the case where the two numbers are allowed to differ, from this anchor’s
own earlier essay.
What “exactly” is claiming, and how it could fail #
Two numbers agreeing is a weak-looking claim, and it is worth saying what would break it, because
both failure modes are real elsewhere in this field.
The prediction could be too low if the numeric phase created an entry outside the allocated
pattern. That is what a moved pivot does, and it is why the anchor’s earlier essay reports a
bound: with dynamic pivoting an entry can appear anywhere, and a code has to be able to grow its
arrays. Quasi-definiteness removes that possibility entirely, because there is no pivot search to
move anything.
The prediction could be too high if a structurally nonzero entry came out numerically zero.
That happens through cancellation, and it happens for real: on a matrix with symmetry or with
repeated values, two contributions to a fill entry can cancel exactly. The symbolic count then
over-allocates, harmlessly, and the two numbers differ.
Neither happens here. The counts agree in both directions at every ordering and every setting of
the slider, which says the allocation is exact rather than merely safe — and an exact allocation
is what lets a code place the factor in a fixed buffer and reuse it across a whole sequence
without checking.
Fig. 4 The other way a symbolic count can be wrong, from the field’s own essay on it.
Minimum degree and reverse Cuthill–McKee both give 63 on this matrix, and the natural order gives
113 — a factor of 1.8. Two things about that are worth saying.
The tie is a property of the shape rather than a coincidence. A bordered band is nearly the case
both heuristics were designed for: RCM minimises bandwidth and the matrix is banded except for
the border, and minimum degree eliminates the low-degree interior first, which for a band is the
same order. On a two-dimensional grid the two part
company decisively, and on an arrowhead they part
company the other way.
The factor of 1.8 is what is being bought, and it is small because the problem is small. Fill
grows superlinearly, so the ratio between a good ordering and a bad one grows with the problem:
on the grids this field measures elsewhere it reaches an
order of magnitude, and it is the difference between a factorisation that fits in memory and one
that does not.
What the page adds is that on this family the ratio is available. A heuristic that produced a
beautiful ordering the numeric phase then abandoned would be buying nothing.
Fig. 5 The orderings ranked, in the field’s own terms.
The constraint rows are what make this a saddle-point matrix and they are also what makes its
graph interesting, so it is worth reading the panels as graphs rather than as pictures.
A constraint touching t unknowns is a vertex connected to t others. Eliminating it makes those t
mutually adjacent — a clique of size t — which is t(t−1)/2 edges, most of them new. So a
constraint row is an expensive vertex to eliminate early and a cheap one to eliminate late, and
both fill-reducing heuristics discover that without being told: in every panel the constraint
vertices are pushed towards the end of the ordering.
That is also why the fill rises with the slider. A constraint touching five unknowns creates a
clique of ten edges where one touching two creates a single edge, so the cost of the border grows
quadratically in how local the constraints are. A model with a few global constraints — a total
that must sum to one, a mean that must vanish — is the worst case: one vertex adjacent to
everything, whose elimination fills the entire remaining matrix.
The theorem needs the matrix to be quasi-definite, and a saddle-point matrix is not: its (2, 2)
block is zero, and zero is not negative definite. The property is bought by perturbing both
blocks — δ added along the primal diagonal, −γ along the dual one — and the perturbation is a real
change to the answer.
The constraint field’s essay measures
what it costs: an error proportional to δ, with the constant computable, and removable by
refining against the unregularised matrix as long as δ stays below σ_min(K). So the price is a
few triangular solves per right-hand side, and a design constraint on δ with both ends known.
There is a second price that is easier to miss. The theorem guarantees the factorisation
exists; it says nothing about the growth, and the growth across five hundred orderings spans
1 to 6.4·10⁵ with the worst residual nine orders above the best. A code that chose its ordering
purely for fill and never looked at the numbers would sometimes get a factorisation that
reproduces its own matrix to seven digits.
So the fight has not been abolished. It has been converted from a constraint on the ordering
into a bound on the regularisation, and the second is a single scalar that can be adapted
during a run.
Fig. 7 The spread of what the orderings are worth, which the fill counts say nothing about.
Why the constraint block cannot simply be ordered away #
A reader who has followed the graph argument may ask why the ordering does not simply put all the
constraint rows last and be done with it, since a constraint vertex is expensive to eliminate
early.
It does, roughly, and that is what both heuristics discover. What it cannot do is make the
constraint rows free, and the reason is the same clique argument seen from the other end.
Eliminating everything else first leaves a dense m × m Schur complement among the constraint
rows — the matrix AH⁻¹Aᵀ that the constraint field’s second
essay forms explicitly — and that block is dense
whenever any two constraints share a variable, whatever order they are eliminated in.
So the fill has a floor of m(m + 1)/2 entries that no ordering removes, and the whole exercise is
about the fill above that floor. On the figure’s matrix with m = 4 the floor is ten entries out
of sixty-three, and on a problem with a thousand constraints it is half a million — at which
point the border, not the interior, is the memory.
That is a shape worth recognising because it changes which method wins. When m is large enough
for the dense Schur block to dominate, factorising the whole matrix stops being cheaper than
the null-space route, and the choice goes back to
being about the two eliminations.
Fig. 8 The floor, drawn: what is left among the constraint rows after everything else has gone.
Against the alternative, which is threshold pivoting #
The other way to factorise a sparse saddle-point matrix accurately is to allow the numeric phase
to depart from the ordering when a pivot is too small, and to accept the extra fill. This
anchor’s threshold essay prices that: every
setting of the threshold buys fill with growth or growth with fill, and there is no setting that
is free.
The comparison is not that one is better. It is that they are different kinds of cost.
Threshold pivoting’s cost is unpredictable: how much extra fill appears depends on the values,
so the allocation cannot be sized in advance, the analysis may have to be repeated, and a
sequence of similar problems can have different memory requirements. Regularisation’s cost is a
number chosen before the run, and refinement removes most of it.
For a sequence of solves that difference dominates everything else, and it is why
interior-point codes regularise rather than threshold. One symbolic analysis at the start, dozens
of numeric factorisations with identical structure, and a memory requirement known before the
first one runs.
Fig. 9 The curve this family gets off, from the anchor’s own essay.
The sequence field asks a related question of a
different family: whether an ordering computed for one matrix is still good for the next one. Its
answer there is that the pattern has to be the same, and when it is, the ordering is reusable
and the pivots are not.
An interior-point sequence is the cleanest possible case of that. From one barrier parameter to
the next, only the p diagonal entries of the (2, 2) block change, and no off-diagonal entry moves
at all — measured, at every step. The pattern is not merely similar; it is identical.
So the symbolic phase runs once for a whole optimisation. And the numeric factorisation, which
the next essay in the sequence field shows
cannot be carried across even a single step, is recomputed each time into an array that never
changes shape.
That is the division this page is really about: a fixed structure and moving numbers, with the
structure computed once. It is what makes a sparse direct method viable inside an outer
iteration, and it is available here because of one line about the signs of two blocks.
Fig. 10 What cannot be carried across a step, from the sequence field.
Predictable fill is usually argued for as an allocation question, and on a modern machine it is
worth more than that.
A factorisation whose pattern is known in advance has a known elimination tree, and the tree
is a task graph: which columns can be factorised independently, in what order, and with what
dependencies. A code can build that schedule once, before any number exists, and then execute it
— on several cores, or on a machine where the cost is words moved rather than operations
counted.
A factorisation with dynamic pivoting cannot. A moved pivot changes the tree, so the schedule has
to be rebuilt, the load balance changes and the communication pattern with it. Codes that do this
well spend a great deal of effort on it, and the effort is the price of the numerical freedom.
None of that appears in a fill count and none of it appears in a residual, which is why it is
worth naming separately. On the family this page is about, the schedule is as static as the
allocation, and both are computed from the graph.
Fig. 11 The other half of what a fixed structure is worth, in the field that counts messages.
The claim to close is the one this anchor established two essays ago and which is true
everywhere except here: a symbolic phase can only bound the fill, because the numeric phase may
move a pivot and every moved pivot adds entries the analysis did not allocate.
The assertion is fed the three pairs — 113 against 113, 63 against 63, 63 against 63 — and
required to reject the claim that they differ. It does.
The refusal is worth reading as a boundary rather than as a correction. The earlier essay’s claim
is right about sparse LU and about symmetric indefinite factorisation with threshold pivoting,
which between them cover nearly everything this field studies. What this page adds is a family
where it fails, and the family is characterised by an algebraic property rather than by a
numerical accident — so it can be checked for rather than hoped for.
Fig. 12 With the most local constraints the figure draws, where the border costs least.
The property is algebraic, so it can be checked for rather than hoped for, and it is worth
knowing which problems have it.
Interior-point methods for linear and quadratic programming, which is where the
regularisation is standard and where the sequence argument above applies in full.
Least squares written as an augmented system — [[I, A], [Aᵀ, 0]] — which is quasi-definite
after regularising the second block and is the stable alternative to the normal equations that
the least-squares field spends an essay on.
Mixed finite-element formulations for flow and for elasticity, where the (1, 1) block is a
discretised operator and is definite, and where a small dual regularisation is often present
already for reasons of the discretisation rather than of the arithmetic.
Where it is not: any problem whose (1, 1) block is indefinite. A saddle point of a nonconvex
objective has a Hessian with negative curvature in it, and no diagonal perturbation of bounded
size makes it definite — a diagonal shift δ would have to exceed the most negative eigenvalue, which
is a change to the problem rather than to its conditioning. Those need the 2 × 2 pivots after all, and the
fight this page describes resumes.
Fig. 13 Negative curvature, from the field where it is useful rather than an obstacle.
Fig. 14 Four, midway along the slider.Fig. 15 The same kind of picture in the field’s own first essay.Fig. 16 How fill grows with the problem, which is why the factor of 1.8 here is a small number about a
small matrix.Fig. 17 The unsymmetric case, where the pivots move and the pattern with them.Fig. 18 The conflict this family avoids.Fig. 19 What eliminating a whole block does to a pattern, which is the alternative to factorising the
matrix entire.Fig. 20 What the orderings cost to compute, which is not free either.Fig. 21 An ordering chosen for a machine rather than for a count.Fig. 22 The price of the property, and its removal.Fig. 23 The matrix underneath, from the constraint field.Fig. 24 And the case where two orderings that tie here part company completely.Fig. 25 A larger problem with more constraints, where the border’s floor is a larger share.Fig. 26 The property being relied on, at a comfortable regularisation.Fig. 27 The sequence the fixed structure is for.Fig. 28 And the routes that avoid the question by not factorising K at all.Fig. 29 The signs the same factorisation produces, put to work.Fig. 30 And the conditioning of the systems this ordering is computed for.