The depth that is worse than both ends

An ordering that buys processors, not time left nested dissection in an awkward position. It loses to minimum degree on fill and on total work at every grid either measurement could draw, and it does not win back the time either: its critical path — the longest chain of work along the elimination tree, which is what a factorisation on unbounded processors takes — is within 28 per cent of minimum degree’s at every size from 8 to 24 points a side. What it wins is the ratio of total work to critical path, which grows from 2.7 to 4.5 where minimum degree’s stays between 2.1 and 2.6.

The essay ended by naming the ordering real codes actually ship. Dissect to a chosen depth, then order each remaining piece by minimum degree, and number the separators last. Sweeping the depth was supposed to put the two numbers on one curve and say whether there is a depth that keeps most of dissection’s ratio for most of minimum degree’s work.

It says there is not, and it says something sharper on the way.

The ordering, exactly as a code writes it #

The least fill there is is the exhaustive answer both endpoints are heuristics for, and it is available only at sizes far below these. The recursion bisects the grid, orders the two halves, and numbers the separator last, which is nested dissection. The hybrid stops the recursion at a chosen depth and orders each remaining sub-rectangle by minimum degree on the subgraph the grid induces there.

“On the subgraph the grid induces there” is the part that has to be right and is easy to get wrong. A vertex on the boundary of a piece has neighbours outside the piece, and counting those neighbours would make its degree depend on variables the piece’s own elimination never touches — so minimum degree run on the whole grid’s adjacency, restricted to the piece’s vertices, is a different and worse rule than minimum degree run on the piece. A real code has the piece as a separate submatrix and never sees the outside, which is what is reproduced here.

Depth zero is then minimum degree on the whole grid, and any depth past the recursion’s own stopping condition is pure nested dissection. So one sweep contains both orderings of the earlier measurements as its endpoints.

One more thing about the construction is worth stating because it is the reason the two ends of the sweep are the right two orderings and not approximations to them. The construction is written for the square grid specifically — it bisects by row or column index rather than finding a separator — so on a grid it produces the optimal separator at every level, and pure minimum degree is the same routine the earlier measurements measured. The sweep therefore contains the two published orderings exactly, with the hybrid between them, rather than three variants of one implementation.

Total work rises, everywhere #

On a 24×24 grid, 576 unknowns, the operation count $\Sigma c_j^2$ against the switching depth:

The least is at depth zero, which is minimum degree, at every one of the four grid sizes measured. There is no interior minimum and no plateau: each level of dissection costs arithmetic.

That is the expected half. Nested dissection’s guarantee is asymptotic — O(n log n) fill on a k×k grid against minimum degree’s heuristic behaviour — and the crossover is known to be well past the sizes a dense symbolic factorisation can afford. What the sweep adds is that the approach to the crossover is monotone rather than dipping.

And the critical path does not fall reliably #

The other curve is the one the hybrid was supposed to earn its place with, and it is not monotone in either direction.

Four sizes, four different answers, and at 20×20 the shortest critical path belongs to minimum degree — nested dissection does not win even the parallel measure there. At 12×12 the best depth is an interior one and both endpoints are worse. At 16×16 and 24×24 the interior optimum is within one per cent of full dissection’s.

So the hybrid’s parallel advantage over full dissection, where it exists at all, is a per cent or two, and which depth supplies it moves with the size in a way four points cannot resolve into a rule. Against that, every level of dissection costs between 4 and 24 per cent of the total work.

The depth that is worse than both ends #

One thing in the sweep is consistent across all four sizes and it was not what the sweep was looking for.

Depth one — a single bisection, then minimum degree on the two halves — is worse than depth zero and worse than full dissection, on work and on the critical path, at every size:

On work it is between the two ends, which is what an interpolation should do. On the critical path it is above both, by 23 per cent at 12×12, 10 per cent at 16×16, 38 per cent at 20×20 and 30 per cent at 24×24.

The mechanism is visible in the widest column of the factor, which the sweep also records: at 24×24 it is 38 with no dissection, 42 at one level, and 35 at three or more. One bisection creates a separator of k vertices whose elimination is a dense k×k block at the top of the tree, and the whole of that block sits on the critical path of every leaf. Below it, the two halves are 12×24 rectangles — still large enough that minimum degree’s own critical path through them is long. So the separator’s cost is added to a path that was not shortened, and the recursion that would have shortened it has been stopped.

At two or three levels the pieces are quarter- and eighth-grids, the separators are shorter, and the paths through the pieces are short enough that the separators dominate — which is the regime nested dissection’s argument is about. One level is in neither regime: it pays a dissection’s cost and gets a heuristic’s parallelism.

It is worth separating two things the parallel measure could mean, because that measurement’s headline number was the ratio and this one’s is the path.

The ratio — total work over critical path — is the most a factorisation on unbounded processors can be sped up by, and it is a property of the tree’s shape. It rises with the dissection depth fairly reliably: at 24×24 it goes 2.52, 2.39, 3.55, 3.67, 4.09, 4.35 across the depths, which is the curve that measurement’s finding was about.

The critical path is the wall-clock those unbounded processors would take, and it is the ratio’s denominator divided into a numerator that is also rising. A deeper dissection improves the ratio partly by increasing the total work, which is not an improvement. That is why the two measures disagree about which depth is best, and why the path rather than the ratio is the one to read when the question is how long the factorisation takes.

What the sweep therefore recommends #

A threshold between fill and growth is the other trade a sparse solver makes at ordering time, and it has the same shape: a parameter with two costs pulling opposite ways and a measurement rather than a rule to set it by.

Not the hybrid, at these sizes, and that is a narrower recommendation than it sounds.

At a few hundred unknowns the arithmetic is small enough that nobody chooses an ordering for it, and the sizes where the choice matters are the sizes where nested dissection’s asymptotics have taken over. The sweep’s value is negative and specific: there is no shallow dissection that is cheap, the interpolation is not monotone in the quantity that matters for a parallel run, and the one depth a code might reach for as a compromise — bisect once, then use the heuristic already to hand — is the worst depth available.

That last point is the practically useful one, because bisecting once is the cheapest thing to implement. A code with minimum degree already written and a graph partitioner to hand can add one level of dissection in an afternoon, and the measurement says the afternoon makes the factorisation slower in both currencies at every size measured.

Where the measurement is weakest #

The bisections are geometric. A real partitioner finds separators in the graph, and on a grid a geometric bisector is the optimal separator, so nothing here penalises the partitioner for being imperfect — every number is nested dissection at its best.

That cuts the other way for the depth-one result. If a perfect separator at one level is worse than none, an imperfect one is worse still, and the finding is a lower bound on the penalty rather than an artefact of a weak bisector.

The critical path is $\Sigma c_j^2$ accumulated along the longest root-ward path through the elimination tree, with no communication cost. The earlier measurement named that omission as its first open question: a critical path charging for the boundary data moved at each separator would penalise dissection, whose separators grow with the grid, and would penalise it most where it currently wins. And the work measure is the same $\Sigma c_j^2$ the earlier measurement minimised exactly, with the same distance between it and a second on any machine — three counters is where that gap is measured.

What a separator costs and what it buys #

The depth-one result is worth one more paragraph of mechanism, because the same arithmetic says where the crossover must be.

A separator of s vertices at the top of the tree is eliminated last, as a dense $s \times s$ block, and costs about $s^3/3$ operations that sit on every leaf’s path to the root. On a k×k grid the first separator has s = k, so one bisection adds about $k^3/3$ to the critical path of everything below it — 4,608 at k = 24. The two halves are k/2 × k wide, and minimum degree’s critical path through a rectangle of that size is not half the path through the square: the elimination tree of a heuristic ordering is tall and thin, and halving the area shortens it by much less than half.

So the ledger at one level is: pay $k^3/3$, save less than half of a path that was already the dominant cost. At two levels the pieces are k/2 × k/2 and the separators are k and k/2, so the payment grows by an eighth while the saving grows toward three quarters. That crossing is where the measured curves turn, and it is why depth two is the first depth that beats depth one.

The same arithmetic says the crossover with minimum degree — where dissection wins outright rather than merely beating its own depth one — is where the separators’ cumulative cost is below the heuristic’s path, which happens when k is large enough that $k^3 \log k$ is below whatever minimum degree’s path grows like. Neither growth rate is measured here, and four grid sizes is too few to fit one.

What this does not settle #

Four grid sizes, one grid shape, and one graph family. Nothing here says anything about a matrix that is not a five-point Laplacian on a square.

The symbolic factorisation is dense — a pattern stored as an n×n boolean matrix — which is what caps the sizes at 24 a side. The asymptotic crossover between the two orderings is at thousands of unknowns, so every number above is from the pre-asymptotic regime by construction, and the monotonicity of the work curve is a statement about that regime.

No numerical pivoting. Every ordering is legal because the matrix is symmetric positive definite.

And the depths are integers on a recursion whose stopping condition also fires when a piece gets small, so depths 5 and above are all pure dissection at these sizes and the sweep has fewer distinct points than it appears to. That is why the tables quote depth 8 and depth 5 as the same ordering, and why the interior optima at 16×16 and 24×24 are one step from the end rather than in the middle.

The widest column is the diagnostic #

The quantity that identifies the depth-one anomaly is not the work or the path. It is the widest column of the factor, and it is worth naming because it is the cheapest of the four to compute and the only one that separates the anomalous depth from every other.

At 20×20 the widest column is 29 at depth zero, 38 at depth one, and 29 again at depths two through eight. At 24×24 it is 38, then 42, then 38, 35, 35. The anomalous depth is the one — the only one — where the widest column is larger than at either end.

That is the separator showing up directly. A separator numbered last is a dense block whose width is the separator’s size, and on a 20-grid that is 20 vertices coupled to both halves’ boundaries, which the elimination fills to 38. At depth two the separators are 20 and 10, and the 10-wide ones are narrower than what minimum degree was producing anyway, so the widest column comes from inside a piece rather than from a separator.

The practical value of that is that a symbolic phase already computes column counts — it is the thing fill is the sum of — so the maximum is free, and it is a single number that says whether an ordering has a dense block at the top of its tree. The order decides the memory reports it as part of every fill report in this field, and this is the first measurement where it distinguishes orderings that the fill count does not: depth one’s fill is between the two ends, and its widest column is above both.

An ordering whose widest column exceeds both of the orderings it interpolates between is an ordering that has introduced a bottleneck neither end has. That is a checkable property, it costs nothing, and it is what the sweep would have found without measuring a critical path at all.

Still open: the separator’s own cost, and a depth chosen from the graph #

Charging for messages. The critical path here is arithmetic only. Adding, at each separator, a cost proportional to the boundary data moved between the processors on either side would turn the speedup bound into something closer to a speedup — and the separators grow with the grid, so the charge grows where dissection’s advantage does. Whether dissection’s ratio survives it is the measurement the earlier measurement asked for and this one has not made.

A depth read off the graph. Four sizes gave four best depths, which is not a rule and might become one if the depth were expressed as “stop when a piece is smaller than m vertices” rather than as a number of levels. That reparameterisation would make the three interior optima comparable, and it is one sweep.

Whether the depth-one penalty survives a real partitioner. Geometric bisection of a grid is the best case. On a graph where the separator is found rather than known, the depth-one ordering has a longer separator and the penalty should be larger — a prediction with a sign, and the cheapest test of whether the mechanism proposed above is the operative one.

And the third objective. Two minima that are one minimum found fill and total work minimised by one order, and noted that the critical path is not a function of the eliminated set and so cannot be minimised by the same search. The hybrid sweep is a one-parameter slice through the space that search cannot reach, and what the true minimum critical path is — over all orderings, not over eight depths — is unknown at any size.