An ordering that does not wait for the numbers

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.

The family, and the line #

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.

The measurement #

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:

ordering predicted counted natural 113 113 minimum degree 63 63 reverse Cuthill–McKee 63 63

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.

One configuration is one pair of numbers, and the claim is about a family.

Over seven configurations — four widths of constraint, two sizes and two constraint counts — that is twenty-one predicted-against-counted pairs and twenty-one exact agreements. Not one of them is a bound.

And the sweep says what the ordering is worth, which the single configuration cannot. As the constraints widen from two unknowns to five, the natural ordering’s fill runs 111, 113, 115, 117 — two entries per unknown added — and minimum degree’s runs 59, 63, 67, 71, which is four. So the saving narrows: 52, 50, 48, 46 entries, and the ratio falls from 1.88 to 1.65. A heuristic that reorders to avoid coupling has less to avoid when everything is coupled.

The other two knobs push the other way. Growing the problem from 24 unknowns to 32 at fixed constraints takes the ratio from 1.79 to 1.84, and going from four constraints to six takes it to 2.14. What a fill-reducing ordering is worth on this family therefore rises with the size and with the number of constraints and falls with their width — three directions, none of which a single measurement reports.

They tie at every one of the seven. Minimum degree and reverse Cuthill–McKee return the identical count in all seven configurations — 59, 63, 67, 71, 79, 71, 43 — which is a property of this bordered band rather than of the two heuristics. They are different algorithms with different objectives, and on a matrix whose graph is a path with a few extra vertices attached there is essentially one good order and both find it. On the field’s own comparison, where the graph is a grid, they do not.

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.

Two orderings that tie, and one that does not #

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.

What the border does to the graph #

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 usual repair for that is to eliminate such a row last and treat it as a low-rank update, which is the same trick another field uses for a different reason.

What is being given up, and it is not nothing #

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.

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.

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.

And the ordering survives the sequence too #

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 what survives one step of the barrier 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.

What a fixed structure buys beyond memory #

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 — or so the argument goes: a moved pivot changes the tree, so the schedule has to be rebuilt, the load balance changes and the communication pattern with it. That is true in kind, and the amount matters, because rebuilding a schedule and repairing seven of its sixty-four edges are different operations.

The elimination tree’s parent array before and after the row permutation the factorisation actually chose, on a conflict grid ordered by minimum degree so the tree branches rather than being a path:

Full partial pivoting moves eleven rows and changes seven parents. Eighty-nine per cent of the schedule survives, so the repair is a handful of subtrees rather than a rebuild — a different engineering problem, and a much smaller one.

And a threshold of 0.3 leaves the tree completely unchanged, at two swaps, with less fill than full pivoting: 360 against 376. So the static schedule is not something dynamic pivoting forfeits. It is something a relaxed threshold buys back in full, and on this matrix it costs nothing in fill to do so.

That reframes the trade rather than removing it. The price of numerical freedom is not the schedule — it is the growth factor, which is exactly what the threshold bounds. Between τ = 1 and τ = 0.3 the schedule goes from 89% intact to 100% intact, and what is given up is the guarantee on the multipliers.

One caution about the measurement, because the first attempt at it was vacuous. On the natural ordering this matrix’s elimination tree is a path, and every permutation of a path is a path, so nothing could change and nothing did. A tree has to branch before a permutation can be seen to perturb it, which is what the minimum-degree ordering supplies.

assertPivotingPerturbsTheTreeRatherThanDestroyingIt measures the whole table, and checks first that the tree branches at all.

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.

The refusal #

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.

Where the family is, and where it is not #

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.