The least fill there is

The order decides the memory ranked four orderings of the grid Laplacian by the size of the Cholesky factor they produce and then said what the ranking could not: finding the ordering with the least fill is NP-hard, every ordering in the table is a heuristic, and nobody expects an algorithm that would fill the bottom row with the true optimum. All three statements are correct. What they leave open is a question that sounds like it belongs to the same territory and does not: how far the heuristics are from the optimum on the matrices where somebody could find out.

NP-hardness is a statement about the worst graph as the graph grows. It does not say that the least fill of a particular graph of twenty vertices is unknowable, and it is not. The number of elimination orders of twenty vertices is 20!, about 2.4·10¹⁸, and no search visits them one at a time. But the fill an elimination produces does not depend on the order in which earlier vertices were eliminated, only on which ones were. There are 2²⁰ such sets — about a million — and a search over them finds the least fill exactly, in under a second.

So the heuristics can be priced. On every grid small enough to search, minimum degree’s factor is the smallest there is. On random sparse graphs of the same size it is the smallest on two thirds of them and within 7.6 per cent on the rest, and the distance it does leave is not a flaw in the rule but a property of how its ties are broken.

A search over sets rather than orders #

The factor of an elimination is decided by the graph. The factor is not sparse put that as the rule that eliminating a vertex joins all of its remaining neighbours to each other, and it has a consequence that makes the exact search possible. When a vertex v is eliminated after a set S of others, the entries it contributes to the factor are the vertices outside S that v can reach by a path whose interior lies entirely in S. That count depends on v and on S. It does not depend on the order in which the vertices of S went.

The least number of factor entries is therefore a shortest path through the sets of eliminated vertices. Start from the empty set; from any set S, eliminating a vertex v not in it costs the size of v’s reach through S and leads to S with v added; the answer is the cheapest way to reach the full set, plus one entry for each diagonal. Every set is visited once and every vertex tried from it once, so the work is about n·2ⁿ reach computations — a million sets on twenty vertices, two million on twenty-one. Each set is stored as the bits of an integer, and a reach is a handful of bitwise operations.

Two checks keep the number honest. The search records which vertex it eliminated last on the way to each set, which recovers an order that attains the minimum; that order is then handed to the ordinary symbolic factorisation, which counts its factor from scratch and must return the same number. And the count the search reports is compared with every heuristic’s, none of which may beat it. On every graph here both hold. The search refuses a graph of more than twenty-two vertices, where the table of sets would no longer fit in the memory a figure can use.

On every grid small enough, minimum degree is optimal #

The three grids with at most twenty-one vertices are the 4×4, 4×5 and 3×7, and minimum degree finds the least fill on all three.

On the 4×4 grid the least fill is 58 entries, and minimum degree reaches 58; so does every one of three hundred random breakings of its ties, and reverse Cuthill–McKee reaches 62 and the natural order 67. On the 4×5 grid the least is 76, minimum degree’s index tie-break reaches 76, and random tie-breaks reach it 133 times in 300 with the worst at 81. On the 3×7 grid the least is 74, minimum degree and every tie-break reach it, and reverse Cuthill–McKee and the natural order reach 84 and 125.

So on the grid — the structure the whole ordering literature was developed on — the ordering nobody can prove anything about is not a heuristic in any practical sense at these sizes. It is the optimum. That is not evidence about large grids, where the separator argument behind nested dissection eventually wins, and the first essay’s table shows nested dissection losing to minimum degree at every size it could draw. What it establishes is narrower and useful: the gap between minimum degree and the best possible ordering on a small grid is zero, so none of the gap between minimum degree and nested dissection at sixteen points a side can be read as minimum degree falling short of an optimum.

On random graphs, two thirds of the time — and the ties hold the rest #

A grid is regular, and regularity is the case a greedy rule is most likely to get right. Random sparse graphs are the harder test, and the search is as cheap on them.

Each graph is a random spanning path on eighteen vertices with twelve further edges added at random, so it is connected and has an average of 3.2 neighbours a vertex. Their least fills run from 56 to 74 entries. Minimum degree with ties broken by index finds the least on 53 of the 80; on the other 27 it is one entry above on twelve, two on eleven, three on three and five on one, and the worst of those is 7.6 per cent above the least. Reverse Cuthill–McKee’s median is 15 per cent above, and on no graph is it optimal.

Forty graphs were not enough to state that share. Two different seedings of forty gave 34 and 28, and the share only settles into the two thirds reported here when both halves of eighty are counted: 28 and 25. A share read from a small sample of graphs is a share of the sample.

The more interesting number is the other one. On all eighty graphs, some breaking of minimum degree’s ties finds the least fill: the best of sixty random tie-breaks reaches it every time. So where minimum degree misses, it misses because at some step several vertices had the smallest degree and the one taken by index was not the one an optimal order takes next. The rule’s criterion — take a vertex of least degree — is never the problem on these graphs. The choice it leaves open is.

How much the ties are worth on a larger grid #

The exact search stops at twenty-two vertices, and the tie-breaks do not. On a larger grid they cannot be priced against the optimum, but they can be priced against each other and against the orderings that compete with minimum degree.

On the 12×12 grid two hundred tie-breaks give factors from 1,005 to 1,085 entries, with a median of 1,039. Ties broken by index give 1,026, which is better than 165 of the 200. The spread of eighty entries is 8 per cent of the median, and it is a fifth of the 387 entries separating minimum degree’s index tie-break from nested dissection’s 1,413. So at this size the ties matter to the tune of a few per cent, and the choice of rule matters to the tune of a third.

The index tie-break is not reliably lucky. On the 8×8 grid its 359 entries are beaten by 113 of 200 random tie-breaks, slightly worse than the median of 357; on the 12×12 grid it is in the best fifth. Which vertex a numbering convention happens to reach first is a property of the numbering, and on the first essay’s grids it happened to favour minimum degree by a few per cent at one size and cost it about as much at another. The table in that essay is therefore a table of minimum degree with one particular tie-break, accurate to about the width of this histogram.

What an NP-hard problem looks like from twenty vertices #

The measurements add up to a picture that is easy to state and easy to over-read.

The optimum is computable on every graph a figure can show. Up to twenty-two vertices the exact search finishes in about a second, and the claim “no algorithm will fill the bottom row with the true optimum” is true only of the rows the first essay could not draw. The order the products are taken in made the same move for contracting a tensor network — two greedy rules priced against the exhaustive answer over many networks — and found a greedy rule close to it there too, which is the shape a hard problem’s typical instances often have.

Minimum degree is optimal on small grids and nearly optimal on random graphs of the same size. Two thirds exactly and none worse than 7.6 per cent, with every miss recoverable by a different tie-break.

None of this is evidence about large graphs. Hardness lives in the tail of instances and in the limit of size, and a greedy rule that is optimal at twenty vertices can be arbitrarily far from optimal at twenty thousand on graphs built to mislead it. The bound that is never attained is the collection’s long-standing lesson about exactly this gap from the other side: a worst case that exists, is attained by a construction, and says nothing about the matrices people meet. The measurement here is the typical case at small size, and it says so.

What the search makes checkable that nothing else did #

There is a practical consequence for anybody who writes an ordering routine, and it is the reason to have built the search at all.

Every claim about an ordering’s quality was until now a comparison between heuristics: minimum degree against nested dissection, an approximate degree against an exact one, a new tie-breaking rule against the old. A heuristic that got better on such a table could have got better than its rivals and still be far from good. On graphs of up to twenty-two vertices there is now a floor to measure against, and a new rule can be scored as a distance from it rather than as a rank. Two ends of the same arrow is the cautionary case in the other direction: one row moved from front to back takes an arrowhead matrix from a dense factor to no fill at all, and any rule that misses such a move on a small graph is now caught by the search, not by intuition.

It also sharpens what the symbolic phase promises. What the symbolic phase can only bound found the fill count exact without pivoting and a bound with it. The least fill found here is a floor under every symbolic count on the same graph, so a code that reports its symbolic count can report, on small graphs, how far above the floor it is.

How far the other orderings are from the floor #

With the least fill known, the first essay’s table can be read as distances rather than ranks, and the distances are not the ones the ranks suggest.

On the three small grids reverse Cuthill–McKee is 6.9, 11.8 and 13.5 per cent above the least fill — 62 against 58, 85 against 76, 84 against 74. It is not a fill-reducing ordering in intent; it minimises bandwidth, and the order decides the memory was careful to say so. What the floor adds is that its side effect on fill is not small change: at twenty vertices it already leaves an eighth of the factor on the table, and on the eighty random graphs its median excess is fifteen per cent.

The natural order is 15.5, 30.3 and 68.9 per cent above: 67, 99 and 125 against 58, 76 and 74. The spread is the grid’s shape. A natural order numbers a grid row by row, its factor is a band as wide as a row, and a 3×7 grid numbered along its seven-point rows has a band more than twice as wide as the same grid numbered along its three-point columns. The least fill does not care which way the grid was numbered, so the natural order’s distance from it is a property of how somebody wrote the matrix down. Elimination is a sequence of choices made the same point about pivots at every step: the algorithm contains a decision whether or not anybody makes it deliberately.

Put the other way round, the savings the first essay credited to minimum degree over the natural order — a quarter of the factor on the smallest grid it drew, rising to nearly a half — are, on grids small enough to search, the savings of the optimum itself: 13, 23 and 41 per cent on the 4×4, 4×5 and 3×7 grids. There is no further saving available on those grids from any ordering at all. On larger grids the floor is out of reach, and the first essay’s saving is a lower bound on what the optimum would save.

Two consequences follow for a sparse solver. The first is that on a small separator block — the kind a multifrontal code factorises thousands of times, and the kind an ordering that does not wait for the numbers orders once from the pattern and reuses — an exact ordering is affordable outright, and there is nothing to be gained from anything cleverer than minimum degree with a tie-break search on top. The second is that once a solver pivots, the pattern it ordered is not the pattern it factorises: a threshold between fill and growth found the pivot threshold buying growth with fill and fill with growth, and a least fill computed from the symbolic pattern is a floor only for the factorisation that follows it.

What was not measured #

The graphs are small by construction: the search’s table has 2ⁿ entries and twenty-two vertices is the most a figure can hold. Every conclusion about minimum degree’s optimality is a conclusion at that size. The random graphs are of one kind — a spanning path and random extra edges, average degree 3.2 — and a family with hubs, or with long cycles, might give minimum degree a different share. The least fill is measured in entries of the factor, which decides memory; the least work, the sum of squared column counts, is a different optimum and may be attained by a different order, which the search as written does not look for. And the tie-breaks here are uniform random choices among tied vertices, where practical codes use approximate degrees and multiple elimination, whose ties fall differently.

Still open: the least work rather than the least fill, and the graphs where minimum degree fails #

The least work. The first essay found the operation count behaving like the square of the fill, so an order with slightly more fill but a shorter heaviest column could do less arithmetic. The same search with the cost of eliminating v after S taken as the square of its reach finds the least work exactly, and the measurement is whether the order that attains it is the same order that attains the least fill, and whether minimum degree is as close to it.

A graph built to mislead the rule. Minimum degree’s known failures are constructions in which a vertex of least degree sits on a separator whose early elimination joins two large regions. At twenty vertices such a construction can be scored exactly, and the question is how large a gap a graph of that size can open — which would say whether the typical-case optimality measured here survives any adversary at this size, or none.

And the ordering that loses on fill. Nested dissection is further from the least fill than minimum degree at every size either essay drew. An ordering that buys processors, not time measures what it buys instead, on the elimination tree a parallel factorisation works along.