A clique has no order

Pieces ordered blind found that one level of nested dissection had been lengthening the critical path of a Cholesky factorisation because its two halves were ordered as if the separator between them were not there. Counting the separator’s vertices in every degree, and numbering them last, cut the depth-one path on the 24 × 24 grid from 53,508 to 41,050 — minimum degree’s own — while the pieces’ own arithmetic did not change.

Every separator in that essay was numbered in index order, and its last section asked about the alternative. “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.”

It is a small measurement and its answer is exactly zero. The more useful part is why, because the reason says which separators could ever have a better order and what to do with them instead.

Twenty-four shuffles, one factor #

The test is the plainest one available. Take a separator, order the pieces by minimum degree with the separator counted in every degree and numbered last, as the earlier essay did, and then number the separator’s own vertices in twenty-four different seeded random orders. For each order, compute the factor’s fill, its total arithmetic and the critical path of its elimination tree — the longest chain of dependent column operations, which is what a parallel factorisation’s time is bounded below by.

The separators are every kind the essays on ordering have produced. The row separators of the 12 × 12, 16 × 16, 20 × 20 and 24 × 24 grids, one grid line across the middle. The level-set separators of the same grids, found from a breadth-first search rather than from coordinates, which on a grid come out as anti-diagonals. And, because a grid has a geometry that might be doing the work, the level-set separators of three random geometric graphs: 300 points scattered in the unit square and joined when they lie within 0.11 of each other, a mesh with no rows, no columns and no symmetry.

On all eleven, the twenty-four orders give one factor. Not a factor within a per cent — the same one. On the 24 × 24 grid the row separator’s fill is 6,273 entries, its work 109,789 and its critical path 41,050 under every shuffle; the diagonal separator’s are 6,229, 107,925 and 36,144 under every shuffle; the first geometric graph’s are 4,739, 103,843 and 51,238. The figure at the top of the page is eleven points on the dashed line at one and four that are not, and the four are a separator built for the purpose, which comes later.

Why a separator has no order #

The reason is a fact about elimination that predates the question. Eliminating a vertex joins all of its remaining neighbours to each other — that is what fill is — so by the time a set of vertices has been eliminated, any two vertices that were connected by a path through the set are joined. Once both pieces of a dissection are gone, two separator vertices are adjacent if some path between them runs entirely through one piece.

A grid row through the middle of a grid has every one of its vertices touching both halves, and each half is connected. So any two separator vertices are joined through either half, every pair is adjacent, and the separator is a clique by the time its first vertex is eliminated. Every column of the factor in the separator’s block is then full: the block is a dense lower triangle of $s$ columns with $s, s-1, \ldots, 1$ entries, whatever order the columns come in. The columns of the pieces are not touched either, because which separator rows a piece’s column fills into is a question about which separator vertices it reaches, not about how they are numbered among themselves. The order inside a clique is the one choice in sparse elimination that is not a choice.

That is a strong statement after essays that began with the opposite one. The order decides the memory put four elimination orders on one matrix and got factors of 1,739, 1,354, 1,413 and 1,026 entries: in sparse elimination the order is usually the whole question, and the four answers were all exact. What makes the separator different is that it is eliminated last, after everything that could connect its vertices has already done so. An order matters only where the graph still has a choice to make about which pairs become adjacent, and at the root of a dissection the pieces have already made all of those choices.

Two minima that are one minimum searched every elimination order of forty small graphs exhaustively and found the order with the least fill was nearly always the order with the least arithmetic. Seen from here, those exhaustive searches spent most of their effort on ties of exactly this kind: whole families of orders that differ only inside sets of vertices that are cliques by the time they are reached, all giving the same factor. The search space of elimination orders is far larger than the space of distinct factors, and a clique of $s$ vertices at the end of an order collapses $s!$ orders into one.

The figure measures that directly. On every grid separator and every geometric graph’s separator, every pair of separator vertices is joined once the pieces are gone: a share of exactly one. That is also why the halves were the price could say both of its first separators “cost exactly 4,900” — $1^2 + 2^2 + \cdots + 24^2$, the cost of a dense triangle of side 24, which a separator of 24 vertices costs whatever its shape and whatever its order.

Minimal is more than the argument needs #

The textbook statement is about minimal separators — those in which every vertex touches both sides — and the geometric graphs show it is stronger than it needs to be. Their level-set separators are not minimal: on the second graph six of thirty vertices touch only one half, on the third ten of thirty-seven. A vertex that touches only one half is still joined, through that half, to every vertex that touches it — and every other separator vertex touches both halves or the same one. So the separator is still a clique, every shuffle still gives the same factor, and the condition that matters is weaker than minimality: every pair of separator vertices must share a piece they both touch.

The drawing shows what a level-set separator on an irregular mesh looks like: a ragged band across the square, a vertex or two thick in places, following the breadth-first search’s level rather than any straight line. On this graph ten of its 37 vertices sit on the band’s far edge where it is thick and touch only one half; on the first graph none of its 36 do. The ten are joined to the rest through the half they touch, every other separator vertex touches that half too, and the band is a clique all the same. A band thick enough that some pair of its vertices touches no common half is the shape the next section takes to its extreme.

Where the order does matter #

To find an order that matters, the separator has to stop being a clique. The simplest way is to make it too thick: two adjacent grid rows through the middle rather than one. Every vertex in the upper row touches only the upper half; every vertex in the lower row only the lower. Two vertices in the same row are joined through their half; two vertices in different rows are joined only if they are directly above one another. Just over half the pairs are joined — 0.511 to 0.522 of them on the four grids — and the separator is far from a clique.

On that separator the order matters a great deal. On the 20 × 20 grid twenty-four shuffles of its forty vertices give critical paths from 22,510 to 32,618; numbering the two rows alternately gives 34,701; numbering them row by row gives 24,265. The order the prediction proposed — each separator vertex chosen by how much fill it carries, which is minimum degree continued into the separator — gives 24,265 too, exactly the row-by-row order, on every grid: once the pieces are gone each row is a clique, every vertex in a row has the same degree, and minimum degree’s ties fall in index order. The best of the shuffles is better than both, by seven per cent on the 20 × 20 grid and twelve on the 12 × 12, which says there are better orders and that the fill-carried rule does not find them.

What the better shuffles buy is worth looking at, because it is not fill. On the 12 × 12 grid twenty-four shuffles of the thick separator give between 1,084 and 1,139 entries, and the smallest is row by row’s own 1,084; on the 20 × 20 they give 4,089 to 4,215 against row by row’s 4,079. No shuffle beats row by row on fill. The shuffles that beat it on the critical path do so with at least as much fill, rearranged into an elimination tree whose longest chain is shorter — the trade an ordering that buys processors, not time found nested dissection making at the scale of the whole grid, made again inside one separator. Row by row is the least-fill order of the thick separator and not its shortest-path order, and on a separator that is not a clique those are two different questions.

The symbolic factorisation answers both before any arithmetic is done. An ordering that does not wait for the numbers found the fill a symbolic phase predicts to be exactly the fill the factorisation produces on matrices of this kind, so every count here — fill, work, path — is a property of the graph and the order alone, and would be the same for any symmetric positive definite matrix with the grid’s pattern.

And every one of them loses to the separator of one row. On the 20 × 20 grid the single row gives a critical path of 22,476 — below the best of twenty-four shuffles of the thick separator, below row by row, below everything — with 3,931 entries of fill against the thick separator’s best of 4,079. On the 24 × 24 grid the single row’s 41,050 is eleven per cent below the thick separator’s best order. The dial shows the same ordering at every size: one row, then the best of the thick separator’s orders, then the rest.

The pattern shows the difference. The single row’s block is a full triangle: 78 entries of 78. The thick separator’s block, numbered row by row, holds 234 of its 300: each row is full against itself, and between the two rows a triangle of 66 entries stays empty. A vertex of the lower row enters an upper column only once the elimination has reached the upper vertex directly above it, because that edge is the only path between the rows that no piece provides; the columns before it never see that lower vertex. Those empty entries are all an order can save — a different order empties a differently shaped set of them — and a separator that is a clique has none to save.

What the separator costs, then #

Since the separator block’s cost is fixed by its size, the one thing worth knowing about it is how large a share of the critical path that size is. On the grids it is a modest one: 4,900 of 41,050 on the 24 × 24 row separator, twelve per cent, and fourteen per cent on the diagonal. On the geometric graphs it is a third to nearly a half — 16,206 of 51,238 on the first, 17,575 of 38,060 on the third — because a level-set separator on an irregular mesh is longer, relative to the graph, than a grid line is: 36 and 37 vertices where a grid with 300 vertices would need about 17. The block grows as the square of the separator’s size in its column counts and the cube in its arithmetic, so a separator a third too long costs more than twice as much at the root of the tree.

That is where the earlier essay’s question belongs. The least fill there is measured how far minimum degree sits from the best possible elimination order on small graphs; at the root of a dissection the best possible order of the separator is any order, and the quantity worth minimising is the number of vertices in it. A partitioner that returns a shorter separator saves what no ordering of a longer one can, and on the thick separator the one-row alternative beat every order tried, at every size — by a hair on the 20 × 20 grid, where the luckiest of twenty-four shuffles came within 34 of it, and by eleven per cent on the 24 × 24.

What this says about the depth-one hybrid #

The question that began this part of the argument was why one level of dissection followed by minimum degree was worse than both no dissection and full dissection. The depth that is worse than both ends blamed the separator; the halves were the price moved the blame to the halves; pieces ordered blind showed the halves were expensive only because they were ordered without the separator in view. This measurement closes the remaining door. The separator’s block cannot be made cheaper by ordering it, only by shrinking it, and on a grid a single row is already the smallest separator there is. What is left of the depth-one penalty, after the halves are ordered with the separator counted, is the separator’s size and nothing else.

An ordering that buys processors, not time found nested dissection’s advantage in the ratio of work to critical path rather than in either alone. The separator blocks are the dense nodes at the top of the elimination tree, where that ratio is decided; they are also, by this argument, the part of the ordering a parallel code can number in whatever order suits its data layout, since no order is better than another.

What these graphs do not show #

Every separator here is the first one, at depth one; a separator deeper in the recursion is a clique for the same reason, provided its own pieces are connected, but nothing here measures one. The thick separator is built by hand to fail the clique condition, and a real partitioner returns something closer to minimal; the geometric graphs show that non-minimal separators from a level structure can still be cliques, but three graphs of one density are a small sample of irregular meshes. The critical path counts each column’s work as the square of its entries, the cost model every essay on ordering has used.

Still open: separators that are not cliques, and a shorter one found #

A partitioner that returns a thick band. Level-set separators on graphs with uneven density can be several vertices thick where the search’s level crosses a dense region, and those vertices touch only one side. The prediction with a sign is that on geometric graphs at twice the density used here — radius 0.16 — at least one level-set separator fails the clique condition, that its order then moves the critical path by more than five per cent, and that trimming every vertex that touches one side into that side shortens the path by more than the best order does.

The separator’s length against its position. On the geometric graphs the separator block is a third to a half of the critical path. A separator found by a spectral bisection — the sign pattern of the graph Laplacian’s second eigenvector — is usually shorter than a level set on an irregular mesh; the prediction is that it shortens the separator by a fifth and the depth-one critical path by more than a tenth, and that the pieces’ contribution, not the block’s, decides which of the two partitions wins.