The halves were the price

A sparse Cholesky factorisation’s cost is decided before a single number is touched, by the order in which the unknowns are eliminated. The order decides the memory measured four orderings on a grid Laplacian and found minimum degree, the greedy one, ahead of nested dissection, the one with the better asymptotics. The least fill there is searched every order on small graphs and found minimum degree at or near the true minimum. An ordering that buys processors, not time measured the elimination tree a parallel factorisation walks, and found that nested dissection’s advantage is in the ratio of total work to critical path rather than in the path itself. Two minima that are one minimum found that fill and total work are minimised by the same order.

Then the depth that is worse than both ends swept the ordering codes actually ship: nested dissection to a chosen depth, minimum degree on the pieces below it. One depth was worse than both extremes on work and on the critical path at every size measured, and it was the first. A single bisection followed by minimum degree on the two halves took longer on unbounded processors than either doing no dissection at all or dissecting all the way down.

The explanation offered was the separator. One bisection creates a separator of k vertices; numbered last, its elimination is a dense k × k block at the root of the elimination tree, and every leaf’s path to the root runs through all of it. Below it the halves are still large, so their own paths are long, and the separator’s cost is added to a path that was not shortened.

That explanation made a prediction with a sign. The grid bisected along its middle row has the shortest separator there is, and a code only gets it when it knows the coordinates. A code handed a matrix finds its separators from the graph, and a found separator should be no shorter and usually longer. If the penalty is the separator, the penalty should grow. This essay makes the test, and the prediction fails — not because the found separator is shorter, but because the separator was never most of the penalty.

A separator from the graph alone #

The oldest way to find a separator without coordinates is George and Liu’s level structure. Pick a vertex far from the rest: start anywhere, run a breadth-first search, restart from a vertex of least degree in the last level reached, and repeat until the number of levels stops growing. The result is a pseudo-peripheral vertex. Number its breadth-first levels. Every edge of the graph joins two vertices in the same level or in adjacent levels, so any single level separates the ones before it from the ones after it. Take the level at which the running count of vertices first passes half the piece. What remains falls into connected components, and each is dissected the same way to the chosen depth and ordered by minimum degree below it.

On a square grid with the five-point stencil a pseudo-peripheral vertex is a corner, and its levels are the anti-diagonals. The level that passes half is the main anti-diagonal, which has exactly k vertices — the same count as a row. So the found separator is no longer than the known one. It is a different shape, and it leaves different pieces: two triangles instead of two rectangles.

Below the first cut the two diverge. The rows-and-columns recursion alternates: a row, then a column in each half, then rows in each quarter. The level-structure recursion finds, in each triangle, a pseudo-peripheral vertex at an acute corner and cuts along the diagonal from it, so the second-level separators of the two triangles line up into the other diagonal of the square and the third level cuts the four resulting triangles across. By the third level the two panels hold different numbers of separator vertices: 16, 15 and 29 on the left and 16, 16 and 22 on the right.

The penalty shrinks #

The critical path is the longest chain of work — the sum of the squared column counts of the factor — along any path from a leaf of the elimination tree to its root, and it is the time a factorisation on unbounded processors takes. At depth one on the 24 × 24 grid it is 53,508 with the middle-row separator and 44,116 with the level-structure one, against 41,072 for minimum degree with no dissection. As a multiple of minimum degree’s path the depth-one penalty is 1.30 with rows and columns and 1.07 with level structures.

The other three sizes agree in direction. At 12 × 12 the depth-one path is 4,850 against 4,553; at 16 × 16, 12,846 against 12,312; at 20 × 20, 27,184 against 24,221. As multiples of minimum degree’s path, 1.23, 1.10, 1.45 and 1.30 with rows and columns become 1.16, 1.06, 1.29 and 1.07. The sign the prediction gave is wrong at every size.

The penalty does not disappear. With level structures, depth one is still worse than no dissection and worse than full dissection on the critical path at all four sizes, so the previous essay’s headline stands with either partitioner. What changes is its size, and what the change says about where it comes from.

Where the depth-one path is spent #

The separator’s share of the critical path can be measured exactly rather than argued about. Numbered last, the k separator vertices form a chain at the root of the elimination tree, and their columns of the factor are dense: the first has k entries, the next k − 1, down to one. Their work is $\sum_{i=1}^{k} i^2 = k(k+1)(2k+1)/6$, and every path from a leaf passes through all of it. So the critical path is exactly that plus the longest path inside either half.

The separator’s cost is identical for the two partitioners at every size — 650, 1,496, 2,870 and 4,900 — because both separators are k vertices eliminated last, and a dense chain of k columns costs the same whatever shape it has in the grid. The whole difference between the two depth-one orderings is inside the halves.

And the separator is not most of the penalty on the larger grids. At 24 × 24 the middle-row ordering’s path exceeds minimum degree’s by 12,436, and the separator accounts for 4,900 of it, under two fifths. At 20 × 20 it accounts for 2,870 of 8,384, about a third. That is the second claim this essay refuses: that the depth-one penalty is the separator’s dense block added to every path. On the two smaller grids the account does hold — at 12 × 12 the block is 650 of a 914 penalty and at 16 × 16 it is 1,496 against a penalty of 1,194, larger than all of it — so the explanation was right where the grids were small and the halves cheap, and wrong where they were not.

What makes up the rest is the path through the halves. With rows and columns, 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. At 20 × 20 it is 24,314 through a half against 18,800 through the whole. Removing half the vertices and letting minimum degree order what is left made its critical path longer. That is what “a path that was not shortened” understated: at the larger sizes the path was lengthened.

With level structures the halves are right triangles, and minimum degree’s path through a triangular half of the 24 × 24 grid is 39,216: shorter than through the whole grid, by five per cent. At 12 and 16 points a side the triangle’s path is also below the whole grid’s, 3,903 against 3,936 and 10,816 against 11,652, and only at 20 is it above, 21,351 against 18,800. Where the triangle’s path is below the whole grid’s, the depth-one penalty is at most the separator’s block, which is the size the previous essay’s explanation assumed it had.

Why minimum degree does worse on a long rectangle than on the square it came from, and better on a triangle, is not explained here. Minimum degree is a greedy rule whose ties are broken by index, and the shape of a piece decides which vertices tie and in what order; eliminating a vertex is a graph operation showed how each elimination joins its neighbours into a clique, and the order in which cliques form on a long thin piece is not the order they form on a square. What is measured is that the shape of the pieces left by the first cut matters more than the cut.

The widest column flags depth one and does not size it #

The previous essay proposed a cheap diagnostic for the anomaly: the widest column of the factor, which a symbolic factorisation computes for free. With rows and columns, depth one was the only depth whose widest column exceeded both ends — 38 against 29 and 29 at 20 × 20, 42 against 38 and 35 at 24 × 24.

With level structures it still flags depth one. At 24 × 24 the widest column is 38 with no dissection, 36 at full dissection and 45 at depth one; at 20 × 20 it is 29, 30 and 33. But it no longer says how bad depth one is. At 24 × 24 the level-structure ordering has the wider column, 45 against 42, and the shorter critical path, 44,116 against 53,508. At 20 × 20 its widest column is five narrower and its path three thousand shorter. The size of the widest column and the size of the penalty move in opposite directions between the two partitioners at 24 and together at 20.

The reason is visible in where that column is. A separator of k vertices numbered last has columns with at most k entries — the first holds the whole separator and nothing else, since everything else is already eliminated. So a widest column of 42 or 45 on a grid of side 24 is not a separator column at all. It belongs to one of the last vertices eliminated inside a half, which is coupled through the fill to the whole of the separator beside it and to what is left of its own half. It is a property of how minimum degree finished the piece, which is exactly the part of the path that differs between the partitioners — and one column’s width is a poor proxy for the path through the hundreds of columns below it.

The diagnostic keeps its use: at no size and with neither partitioner is there a depth-one ordering whose widest column is not above both ends. It says that an ordering has a bottleneck neither end has. It does not say how long the bottleneck makes the path, and ranking two orderings by it would have ranked these two the wrong way round at 24 × 24.

The speedup bound — total work over critical path, the most a factorisation on unbounded processors could gain — moves the other way too. At depth one on the 24 × 24 grid it is 2.39 with rows and columns, below minimum degree’s 2.52, and 2.78 with level structures, above it.

The rest of the depths, and the total work #

On total work, minimum degree with no dissection is still the least at every size with either partitioner: 103,481 at 24 × 24. Every depth of dissection costs more. But the level-structure separators cost less than the rows and columns at every depth of two or more and at every size from 16 up. At 24 × 24 and full depth the level-structure ordering does 115,899, twelve per cent above minimum degree; the rows-and-columns ordering does 149,517, forty-four per cent above.

On the critical path the level-structure hybrid’s best depth is full dissection at all four sizes — 3,596, 8,935, 17,385 and 31,970 — where the rows-and-columns hybrid’s best depth wandered from two at 12 × 12 to none at 20 × 20 to four at 24 × 24. The sweep that looked as if it had no rule to it with one partitioner has a simple one with the other: with level structures, dissect all the way.

Across the four sizes, full level-structure dissection has the shortest critical path of the three orderings, and its total work sits between minimum degree’s and the rows-and-columns dissection’s at every size. At 24 × 24 it takes 31,970 on the path against minimum degree’s 41,072, more than a fifth less, for twelve per cent more work.

It does this with more separator vertices, not fewer. At 24 × 24 the full level-structure recursion places 292 vertices in separators against the rows-and-columns recursion’s 240. The fill that is not independent measured what eliminating both halves leaves on a separator — a dense block — and a longer total of separators should mean more dense blocks. The measurement says otherwise, and the reason is again the shape of the pieces, not the length of the cuts.

What this changes about the previous essay #

The previous essay’s finding — depth one is worse than both ends — survives. Its explanation is half right. On the smaller grids the dense separator block is the penalty. On the larger ones the penalty is mostly minimum degree’s own path through the halves the bisection leaves, and the reason a found separator does better is that it leaves halves minimum degree handles better, not that it is a better separator.

That also changes the cheapest test the previous essay proposed. It expected a real partitioner to be a worse case than geometric bisection, and on a grid it is the better case. A partitioner that knows nothing about coordinates found a cut of the same size whose pieces suit the greedy ordering underneath, and its advantage grows with the depth. An ordering that does not wait for the numbers made the point that an ordering is computed from the graph alone; here the graph alone did better than the coordinates.

What this rests on #

Square grid Laplacians with the five-point stencil, 12 to 24 points a side; nested dissection to depths 0, 1, 2, 3, 4 and 8, minimum degree with ties broken by index on each piece’s induced subgraph; symbolic factorisation computed exactly; work and critical path as sums of squared column counts, with no charge for communication. The level-structure partitioner is the simplest one there is: no refinement of the separator, no balancing beyond taking the level that first passes half. Real partitioners refine and would produce different cuts. Only grids are measured, and a grid is a graph whose level structures are unusually regular.

The claims that have to fail #

The first is the previous essay’s prediction, that a found separator lengthens the depth-one critical path. On the 24 × 24 grid it is 44,116 with the level-structure separator against 53,508 with the middle row; the refusal is fed the claim that the found separator’s path is longer, and fails.

The second is the explanation behind it, that the penalty is the separator’s dense block. On the same grid the block is 4,900 of a 12,436 penalty; the refusal is fed the claim that the block is more than half the penalty, and fails.

Still open: why the shape of a piece decides minimum degree’s path, and graphs that are not grids #

Minimum degree on a rectangle and on a triangle. The whole difference between the two partitioners at depth one is minimum degree’s critical path through the pieces, which is longer through a 12 × 24 rectangle than through the 24 × 24 square and shorter through a triangle. Measuring that path against the aspect ratio of a rectangle, and against the tie-breaking rule, would say whether it is a property of the shape or of the index order in which ties fall.

A graph with no geometry. On a grid the level structures are anti-diagonals and the found separator is the same length as the known one. On an irregular mesh or a random geometric graph the middle level of a level structure is usually longer than the best separator, which is the case the previous essay’s prediction was really about. Whether the depth-one penalty grows there, now that the separator is known to be only part of it, is the next measurement.

Charging for messages. Every critical path here is arithmetic only. A separator’s cost in a distributed factorisation includes moving the boundary data to it, which is proportional to its length and grows with the grid, and the level-structure recursion places more separator vertices than the rows-and-columns one. Whether its lead on the critical path survives a charge for communication is still unmeasured.