Two minima that are one minimum

The order decides the memory measured four orderings on one matrix and found factors of 1,739, 1,354, 1,413 and 1,026 entries. It also measured the operation count, and noted that it behaves like the square of the fill: a column of $L$ with $c$ entries costs about $c^2$ operations to produce, so the total work is $\sum_j c_j^2$ where the fill is $\sum_j c_j$.

A sum of squares and a sum are not minimised by the same thing in general. $\Sigma c_j$ is indifferent to how the entries are distributed among the columns and $\Sigma c_j^2$ is not: a factor with one column of twenty and nineteen of one has the same fill as one with twenty columns of two, and eight times the arithmetic. So the question the least fill there is left was whether the least-fill order is also the least-work order, and the reasonable expectation was no.

The expectation is wrong, and it is wrong rather decisively.

Searching the second minimum #

A threshold between fill and growth is what happens to all of this when a pivot has to be chosen for stability as well, and it is the reason a solver’s ordering phase is separate from its numerical one. The first minimum is already available. The least-fill search is a recursion over subsets: the least number of off-diagonal factor entries contributed by eliminating a set S first, in any order, is a function of S alone, because eliminating v next contributes the number of vertices outside S ∪ {v} that v reaches through S — which depends on S and v and not on the order within S. So f(S ∪ {v}) = min over v of f(S) + |reach(v, S)| over 2ⁿ sets, and the answer is n + f(everything).

The work minimum has the same structure and needed only a different cost. Eliminating v after S produces a column of c = |reach(v, S)| + 1 entries, and a right-looking elimination does $c^2$ operations on it. So the recursion is the same with $c^2$ in place of $c$, and the total is the sum of those squares.

That the second cost also depends on (v, S) alone is the whole reason this is searchable, and it is worth saying that it very nearly is not. A cost that depended on the order within S — the number of updates applied to a column, say, rather than its final height — would not collapse onto 2ⁿ states, and the search would be over n! orders rather than 2ⁿ subsets. At n = 16 that is 20,922,789,888,000 against 65,536.

The recovered order is counted again, symbolically and independently, and required to produce the number the recursion claimed. That check is the one that would catch a recursion which is correct about its own recurrence and wrong about the factorisation.

One thing the second search needed that the first did not is a wider counter. The fill recursion counts into a sixteen-bit array because a factor of a twenty-two-vertex graph cannot hold 65,535 entries, and the array is 2²² entries long so the width matters. Work can exceed that easily — the 3×7 grid’s least-work order does 274 operations and a deliberately bad one does thousands — so the work recursion counts in doubles, at four times the memory. On a sixteen-vertex graph that is half a megabyte against an eighth, which is nothing; at twenty-two it is thirty-four megabytes against eight, which is why the search stops where it does.

The two minima coincide #

On every grid small enough to search — 4×4, 4×5, 3×6, 3×7, 2×9 — one order attains both:

A grid is regular, so a coincidence on grids is suggestive of grids rather than of orderings. On forty random sparse graphs of sixteen vertices with ten extra edges beyond a spanning tree, one order attains both minima on thirty-nine. On the fortieth the least-fill order does 1.0099 times the least work — a one per cent penalty — and the least-work order’s fill is exactly the least fill.

So the asymmetry is one-sided. There exists a graph where minimising fill costs a little arithmetic, and no graph in the forty where minimising arithmetic costs any fill.

Why they coincide, and what would break it #

The mechanism is not subtle once the recursion is written down. The cost of eliminating v after S is $c$ for fill and $c^2$ for work, and $c^2$ is a strictly increasing function of $c$. So at every step of the recursion, the vertex that minimises the contribution to fill is the vertex that minimises the contribution to work — at that step.

That is not enough to make the minima coincide, because the recursion is over subsets and a greedy step-by-step argument proves nothing: choosing the cheapest vertex now can leave a more expensive set behind. What it does is make the two objectives aligned at every decision, so the two searches, exploring the same 2ⁿ lattice, are ranking candidates identically almost everywhere and can only diverge where two vertices have contributions that are ordered differently under $c$ and $c^2$. Under a strictly increasing map, they cannot be — a single pair of contributions is ordered the same way either way.

Divergence therefore requires a sum to be ordered differently from the sum of squares: two whole orders where one has smaller $\Sigma c$ and the other smaller $\Sigma c^2$. That is possible and the fortieth graph does it. It requires the two orders to have genuinely different column-height distributions, and on a sparse graph of sixteen vertices the distributions are too constrained for the difference to reach one per cent more than once in forty.

What the heuristic misses #

Which makes the practical question not “which objective” but “how close is the heuristic to the one objective”, and the answer has a shape worth having.

Minimum degree attains the least fill on 33 of the 40 graphs and the least work on 33 — and they are the same 33. There is no graph in the forty where it gets one right and the other wrong, which is the same alignment argument one level down: a greedy rule ranking candidates by degree is ranking them by the same order under either cost.

Its overshoots differ, and by roughly the factor the squaring predicts. The worst fill overshoot is 1.0526 and the worst arithmetic overshoot is 1.1233 — a five per cent miss in fill becoming a twelve per cent miss in work. The median of both is exactly one, because on 33 of 40 graphs there is no overshoot at all.

So a fill-reducing ordering is a work-reducing ordering, and a fill-reducing ordering’s error is roughly doubled when read as a work error. Both halves matter for a code: the first says there is one thing to optimise, and the second says the stakes are twice what a fill count suggests.

That last figure is worth keeping in view because it changes what “optimal on 33 of 40” means. Minimum degree’s ties are frequent — a sparse graph has many vertices of equal least degree — and the rule that resolves them is not part of the heuristic’s statement, exactly as the tie-break in partial pivoting is not part of that rule’s statement. The 33 is one tie-breaking stream’s result. An earlier measurement here found that on every one of eighty graphs some breaking of the ties reaches the exact minimum, which makes the heuristic’s failure a failure of the tie rule rather than of the degree criterion — and means the alignment result above holds for a family of heuristics rather than for one.

Why the squaring does not double the risk further #

The overshoot relation deserves a sentence, because “work is the square of fill” would suggest a 5 per cent fill overshoot becomes a 10.25 per cent work overshoot and the measurement says 12.33.

The reason it is not exactly the square is that the relation is between sums, not between terms. If every column grew by the same relative factor r, then $\Sigma c$ would grow by $r$ and $\Sigma c^2$ by $r^2$, so the overshoot would square exactly. A heuristic does not overshoot uniformly: it produces a few columns much taller than the optimal order’s and most of them the same height, so the extra fill is concentrated and the extra work is concentrated in the same columns — where $c^2$ responds more than $r^2$ would predict.

That is the same concentration that makes the sum of squares worth caring about at all, and it is why the observed factor is above the square rather than below it. A heuristic whose extra fill were spread evenly would land under the square.

What this settles for a code #

Three things, and the first is the one that saves work.

A sparse direct solver chooses its ordering once, before any arithmetic, from the pattern alone. The measurement says it has one objective to choose against rather than two, so the symbolic phase does not need to compute an operation count in order to rank candidate orderings — the fill count ranks them identically on 39 of 40 graphs and within one per cent on the fortieth. That is a real saving in the symbolic phase, where counting fill is a union of bitsets and counting work is a sum of squares over the result.

Second, the fill count understates the stakes by about a factor of two. A code reporting that its ordering achieves 5 per cent more fill than some reference is reporting 12 per cent more arithmetic, and a user comparing two orderings on a fill count is comparing them on a compressed scale.

Third, and this is the negative one: none of the above extends to the parallel case, because the critical path is not a function of the subsets. A code choosing an ordering for a parallel factorisation has a genuinely different objective, which is the next essay.

What a sum of squares is doing in a fill essay #

The measure $\Sigma c_j^2$ deserves a defence, because it is a model of arithmetic rather than a count of it, and the whole comparison in this essay is between two models.

A right-looking Cholesky, having computed column j of L, subtracts an outer product from the trailing submatrix. The outer product touches the entries where two nonzeros of column j meet, which is $c_j^2$ of them counting the diagonal, and each touch is a multiply and a subtract. Summed over columns that is $\Sigma c_j^2$, and the standard operation count for a sparse Cholesky is exactly that with a factor of a half for symmetry.

What the model leaves out is every constant a real factorisation is made of. It does not know that the subtractions for a supernode are one matrix–matrix product rather than many small ones, that a column stored by index costs an indirection per entry where a dense block does not, or that a factorisation short enough to fit in cache costs nothing to move. Three counters is where those diverge in this field, and the divergence is larger than the 12 per cent this essay’s worst overshoot is about.

So the honest statement of the result is narrower than “ordering for fill is ordering for speed”. It is that the two counting models the field uses — entries and operations — have the same minimiser, so a symbolic phase does not have to choose between them. Which of the two predicts a second on any particular machine is a different question that neither minimum answers.

What this does not settle #

Sixteen vertices, and fourteen, because 2ⁿ subsets at n = 22 is four million states with a reach computation at each and n = 24 is beyond a Uint32 bitmask. Forty graphs, one edge density, and one random-graph model.

The work measure is $\Sigma c_j^2$, the leading term of a right-looking Cholesky’s arithmetic. It is not the flop count of any particular implementation: a left-looking factorisation does the same arithmetic in a different order, a supernodal one does more of it as matrix–matrix products, and none of those changes $\Sigma c_j^2$ but all of them change what a second costs. The three counters is the standing warning about that gap.

No numerical pivoting anywhere. Every order above is legal because the matrices are symmetric positive definite by construction, and a threshold between fill and growth is what happens to all of this when the pivot has to be chosen for stability as well.

And the fortieth graph is one graph. That there exists a graph where the two minima differ is established; how far apart they can be is not, and 1.0099 is the largest gap in forty rather than a bound.

The recursion is the argument #

A word about why an exhaustive search is the right instrument here and not merely the strongest available one.

The claim at issue is a claim about non-existence: there is no ordering with more fill and less work. A heuristic comparison cannot establish it, because two heuristics agreeing says only that neither found the counterexample. A proof would establish it and no proof is offered — the alignment argument above shows the two costs rank single steps identically and explicitly does not extend to sums. So what is left is enumeration, and at sixteen vertices enumeration is affordable.

What makes it affordable is the subset collapse, and the collapse is a fact about the two cost functions rather than about the search. Both are additive over steps, and both terms depend on the pair of the vertex and the set only. Change the cost to anything that reads the order within the set — the number of times a column is updated, the memory traffic a real code moves, the depth of the elimination tree — and the state space becomes n factorial and the question becomes unanswerable at any size worth asking about. The measurement in this essay exists because the quantity it is about happens to have the right shape, and the quantity the next essay is about does not.

That is also why forty graphs is not the weak part of the result. Each of the forty is settled exactly: not sampled, not searched heuristically, but decided over all 65,536 subsets with the recovered order counted again independently. The uncertainty is in how representative forty graphs are, not in whether any of the forty is right.

Still open: how far apart they can get, and the same question for the tree #

A graph built to separate them. The alignment argument says divergence needs two orders whose column-height distributions differ enough for a sum and a sum of squares to rank them differently. A construction aiming at that — one order with a single tall column and another with several medium ones, at the same total — would say how large the gap can be made at sixteen vertices, and whether it grows with the size.

The critical path as a third minimum. An ordering that buys processors, not time measured the longest chain of work along the elimination tree, which is what a parallel factorisation takes. That cost does not depend on (v, S) alone — it depends on the tree, which depends on the whole order — so the same search cannot find its minimum, and whether a different formulation can is the open question that would complete the trio.

Whether minimum degree’s seven failures share anything. Seven of forty graphs defeat the heuristic on both counts. Whether they have a structural feature in common — a vertex of least degree on a separator, which is the known failure mode — is answerable at this size by looking, and would turn “optimal on 82 per cent” into a statement about which 18 per cent.

And the same measurement on a family with structure. Every graph here is random. A banded matrix, an arrowhead, or a grid with a few long-range edges would each have a very different distribution of column heights, and the alignment between the two objectives is an argument about distributions.