Pieces ordered blind

The depth that is worse than both ends swept the ordering sparse direct solvers ship — nested dissection to some depth, then minimum degree on each remaining piece — and found one level of dissection worse, on a grid’s parallel critical path, than both no dissection and full dissection. The halves were the price then took the depth-one path apart. The separator’s own dense block — $\sum_{i=1}^{k} i^2$, paid on every path — was under two fifths of the penalty at 24 × 24. The rest was the path through the halves: “minimum degree’s longest path inside a 12 × 24 rectangular half of the 24 × 24 grid is 48,608 — longer than its 41,072 through the whole grid, twice the size.” With the separator found from level structures the halves were triangles and the path was shorter. The essay could not say why a smaller piece had a longer path, and left the question as one of shape or of the order in which ties fall.

It is neither, and the evidence is one number the earlier essay did not compute.

The half, alone #

Minimum degree run on a 12 × 24 grid by itself — the same rectangle, a matrix of its own — produces an elimination tree whose critical path is 12,913 (in the units every essay in this field uses: the sum of the squared column counts along the heaviest chain from a leaf to the root). On the 24 × 24 grid it is 41,072. A rectangle of half the size has a path under a third as long, as it should.

So the 48,608 is not a property of the rectangle. It is a property of the rectangle inside the dissection, where its columns do not end at its own rows. The half is eliminated first and the separator row last, and every column of the half that touches the separator — directly, or through fill — holds entries in the separator’s rows. Those entries are part of the column’s count, the count is squared, and the path carries them all the way up the tree.

That is where the ordering matters. The depth-one hybrid orders each half by minimum degree on the subgraph the half induces, which is what a code does when it hands pieces to a sequential orderer. A vertex on the edge of the half has three neighbours in the half and one in the separator; in the induced subgraph its degree is three, lower than an interior vertex’s four, so minimum degree eliminates the edge early — and in eliminating it joins its separator neighbour to all of its remaining neighbours, which spreads the separator’s rows into the half’s columns before anything has been done to keep them out.

The ordering itself records this. Of the 48 vertices of the 24 × 24 grid’s halves that touch the separator, minimum degree on the induced subgraphs eliminates 14 in the first quarter of the halves’ elimination; on the 16 × 16 grid, 9 of 32. They are the vertices it sees as cheap, because it does not see a quarter of their neighbours. Once they go, their separator neighbours are joined to the vertices beside them, those vertices’ degrees rise, and the fill that follows carries separator rows through the half from its edge inward.

Counting the separator #

The repair is the one production orderers use for exactly this situation, usually under the name of a halo: minimum degree on the whole graph, with every separator vertex counted in every degree it contributes to but forbidden from being chosen until the pieces are done. The pieces are then ordered knowing what each elimination will do to the separator’s rows. Nothing else changes — the same separators, the same depth, the same tie-breaking by index, the same separator order at the end. The edge vertices are still eliminated, and still before the separator; they are simply no longer mistaken for cheap. Of the 48 on the 24 × 24 grid, the constrained ordering eliminates 4 in the first quarter of the halves’ elimination instead of 14, and 4 of 32 instead of 9 on the 16 × 16 grid. Most of them now go late, when the fill around them has already been decided by the interior and their separator rows have fewer columns to spread into.

The separator vertices are counted but not chosen, and that distinction is the whole design. A separator vertex chosen early would destroy the dissection’s structure — its whole point is to be eliminated last, so that the two halves never meet — and one ignored in the degrees leaves the orderer blind. Counting without choosing gives the orderer the information of the whole graph and the constraint of the dissection together, which is what the hybrid was supposed to have all along.

On the 24 × 24 grid the depth-one path falls from 53,508 to 41,050. Minimum degree on the whole grid is 41,072: one level of dissection, ordered this way, is no longer worse than no dissection at all. At depth two the path falls from 37,933 to 32,889 — below full dissection’s 34,572, and the shortest path of any ordering measured on this grid. Depth three falls from 40,579 to 33,386, depth four from 34,324 to 33,936, and full dissection’s depth eight, where the pieces are too small for the ordering to matter much, from 34,572 to 34,154. The anomaly the earlier essays chased — a depth worse than both ends — is almost entirely an artefact of ordering pieces blind.

Where the saving comes from #

The split settles which half of the account is right. Counting only the entries in each column that lie in the piece’s own rows — plus the separator’s own block, which is the same for both orderings — the depth-one path through the 24 × 24 grid is 17,813 with the halves ordered alone and 17,814 with the separator counted. The constrained ordering does no better inside the halves. At the smaller grids it does slightly worse there: 4,973 against 4,621 at 16 × 16, 10,525 against 9,084 at 20 × 20, because it sometimes accepts a little more fill inside a piece to keep the separator’s rows out.

All of the saving is the rest of the bar. With the halves ordered alone, the separator rows in their columns add 35,695 to the 24 × 24 path; with the separator counted, they add 23,236. The rectangle was never the problem, and neither was the order in which ties fall inside it. The problem was an orderer that could not see the cost of what it was doing to the rows it was not ordering.

The count of those entries is the simplest statement of the difference. With each half ordered alone the factor holds 372, 729, 1,297 and 1,980 entries in the separator’s rows below the halves’ columns on grids of 12, 16, 20 and 24; with the separator counted, 247, 492, 839 and 1,359 — a third fewer at every size. Each such entry lengthens a column whose count is then squared, and the columns that hold the most of them sit at the top of the half’s elimination tree, on every path to the separator. A third fewer entries there is a fifth to a quarter less critical path — 0.76, 0.80, 0.83 and 0.77 times the blind ordering’s at the four sizes.

Work, as well as the path #

The parallel path is what the earlier essays measured; the total arithmetic is what a single processor pays, and the constrained ordering lowers it at every depth as well. At depth one the 24 × 24 factorisation costs 109,789 instead of 127,956; at depth two 113,450 instead of 134,653; at depth eight 141,591 instead of 149,517. Minimum degree on the whole grid, at 103,481, is still the cheapest in total — dissection always buys its parallelism with extra work, as an ordering that buys processors, not time measured — but the price of the parallelism is now much smaller. At depth two the constrained hybrid costs 9.6% more work than minimum degree and has a critical path 20% shorter; ordered blind, the same depth cost 30% more work for a path 8% shorter.

That changes the recommendation two minima that are one minimum implied for how deep to cut. With pieces ordered blind there was no depth that improved on both ends at once. With the separator counted, depth two at 24 × 24 has the shortest path of anything measured and costs less work than any deeper dissection.

Both partitioners #

The earlier essay’s second finding was that level-structure separators, which leave triangular halves, gave a shorter depth-one path than rows and columns. That survives, and shrinks. Ordered blind, the level-structure hybrid’s path is 1.06 to 1.29 times minimum degree’s and the row-and-column hybrid’s 1.10 to 1.45; with the separator counted, 0.84 to 1.13 and 0.88 to 1.20. Both improve at every size, and at 12 × 12 and 24 × 24 both constrained hybrids match or beat minimum degree on the whole grid. Ordered blind, the level structures led at every size; once the orderer sees the boundary neither is consistently ahead — row separators are better at 16 × 16, level structures at the other three sizes, by six to twelve per cent. The consistent advantage of the triangles was mostly an advantage in how a blind orderer met their boundary.

The one size that resists is 20 × 20, where even the constrained orderings stay 13 to 20 per cent above minimum degree at depth one. On that grid the halves are ten rows deep with the separator taking the eleventh, and the constrained ordering pays for keeping the separator out with more fill inside the pieces — 10,525 against 9,084 on their own path — than it saves at their top. The rule “count the separator” is not free; on this grid it is not quite enough.

What a machine with a few processors gains #

The critical path is a lower bound on the time with unlimited processors, and total work over the number of processors is a lower bound with any number; with $p$ processors the time is at least the larger of the two. On the 24 × 24 grid that turns the measurements into a ranking. On two processors the work term dominates everything and minimum degree on the whole grid is fastest, at 51,741, with the constrained depth-one hybrid next at 54,895; no dissection pays on two processors. On four the path takes over, and the constrained depth-two hybrid is fastest at 32,889 — 20 per cent under minimum degree’s 41,072 and 12 per cent under full dissection’s 37,379. On eight it is still the fastest, now 5 per cent under full dissection’s 34,572. The four fastest orderings on four and eight processors are all constrained hybrids, at depths two to eight.

Ordered blind, the same comparison came out differently: on four processors the best blind hybrid was depth four at 35,106, barely ahead of full dissection, and the case for stopping the dissection early — the case the shipped hybrid exists to make — was close to nothing. The earlier essays’ measurements were a fair verdict on the hybrid as it is often glued together. They were not a verdict on stopping the dissection early, which with the pieces ordered properly is the best thing to do on a modest machine.

What the ordering question was all along #

A reordering is a decision about which eliminations happen first, and eliminating a vertex is a graph operation is the reminder that each one joins all of its remaining neighbours into a clique. An orderer that does not see some of those neighbours makes that decision with a wrong count of what the clique will cost. The order decides the memory found the fill of four orderings differing by 70 per cent on one matrix; here the difference is between one orderer seeing a vertex’s neighbours and not, on the same pieces, and it is worth a quarter of the critical path.

The broader lesson is about interfaces. Nested dissection and minimum degree were each designed as a whole-matrix ordering; the hybrid glues them by handing pieces from one to the other, and the glue loses exactly one piece of information — the boundary. The least fill there is measured how close minimum degree comes to the optimum on small graphs when it sees the whole graph; given only part of it, it was optimising the wrong graph, and the earlier essays measured the consequences of that and attributed them to geometry.

The same caution applies to every ordering computed in stages. An order fixed before the numbers found a static minimum-degree order matching a dynamic pivot rule’s fill on a saddle-point matrix, and credited the order with seeing the whole sparsity pattern at once; here the order that saw only part of the pattern lost a quarter of its critical path. Whenever an ordering is assembled from orderings of parts — a dissection’s pieces, a domain decomposition’s subdomains, the blocks of a block-structured solver — the question to ask of the glue is whether each part was ordered with its boundary in view. The cost of the answer being no is not a small correction: on these grids it was larger than the separator’s own dense block, the quantity every earlier account of the depth-one penalty started from.

It is also a cost that no single-part measurement would reveal. Each half, ordered blind, is ordered well as a graph of its own — 12,913 on the critical path of a 12 × 24 grid is an excellent result for that grid. The loss appears only when the half is put back where it came from, and it was measured, in the earlier essay, as a property of the half. That is the characteristic shape of an interface error: every component passes its own test, and the system fails on what crosses between them.

What grids and one tie rule do not show #

Grid Laplacians from 12 to 24 a side, one tie-breaking rule — lowest index — and one family of separators at each depth, with the level-structure family at depth one only. The critical path is the arithmetic model of every essay in this field, with no charge for moving data. The constrained ordering here is exact minimum degree with the separator excluded from selection; production orderers use approximate degrees and multiple elimination for speed, and their tie-breaking differs, so the numbers would move and the direction, on this evidence, would not. And 20 × 20 is a size where the rule is not enough, which says the account is incomplete.

Still open: the 20 × 20 exception, graphs without geometry, and the separator’s own order #

The grid where counting is not enough. At 20 × 20 the constrained depth-one path is still 20% above minimum degree’s. The prediction with a sign is that the halves’ own extra fill there — 16% more path inside the pieces — comes from ties among the vertices adjacent to the separator, and that breaking those ties toward the vertices farthest from the separator removes it.

A graph with no geometry. On an irregular mesh the separator found by level structures is usually longer than the best one, and a longer separator is a longer boundary for a blind orderer to mishandle. The prediction is that the constrained ordering’s advantage grows there, which would make it more important exactly where the earlier essay expected the separator to matter most.

The order inside the separator. Every separator here is numbered in index order, and its vertices form a dense block at the root either way. Ordering the separator’s own vertices by how much fill each carries in from the pieces would shorten the block’s own path; whether by enough to matter against the pieces’ contribution, now that the pieces’ contribution has been cut by a quarter, is a small, direct measurement.