The spare vertices lean one way

A clique has no order found that the order of a separator’s own vertices, in a nested dissection, does not matter — and found why, in a fact about elimination. Once the pieces on either side of a separator are eliminated, two separator vertices are joined in the factor if they were adjacent or if some eliminated piece connects them. A separator whose every vertex touches both pieces is therefore a clique by the time its first vertex is reached, and the order inside a clique changes no entry of the factor. On grids, on the diagonal separators of grids and on three random geometric graphs, every separator the dissection drew was such a clique, and twenty-four shuffles of each moved nothing. The one separator that was not was a band two rows thick through a grid, built by hand.

Its closing question was where a dissection would draw one of those itself. “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 vertices it described are there. The failure it inferred from them is not, and the reason is a fact about level sets.

Twenty-four separators #

The graphs are the earlier essay’s construction: 300 points uniform in the unit square, joined when closer than a radius, as a graph Laplacian. Eight seeds at each of three radii, 0.11 as before, 0.13 and the prediction’s 0.16; the edge counts run near 1,500, 2,100 and 3,100, so the densest graphs have twice the edges of the sparsest. Each is cut once, by the hybrid level-set separator the earlier essays used — a breadth-first level structure from a peripheral vertex, cut at the level that best balances the two sides — and the pieces are ordered by minimum degree with the separator last.

The separators have 24 to 58 vertices, and most of them have vertices that touch only one piece: as many as thirteen on one graph at the sparsest radius, ten on several. So the prediction’s first premise holds at every density measured, not only at the densest. And the clique share is exactly one on all twenty-four. Not a single pair of separator vertices is left unjoined once the pieces are gone.

Density moves the two counts in opposite directions. The separators grow with it — a mean of 34 vertices at radius 0.11, 40 at 0.13 and 49 at 0.16 — because a band one breadth-first level thick holds more vertices when each vertex reaches further; and the spare vertices among them fall, from a mean of 5.0 to 2.4. As a share of the separator, the spares are 15 per cent at the sparsest radius and 5 per cent at the densest. So the prediction’s picture, of a dense graph’s level sets carrying many vertices that separate nothing, has the trend backwards: denser graphs draw bigger separators with proportionally fewer passengers.

Why a thick level set is still a clique #

A level-set separator is a band of vertices at one breadth-first distance from where the search began. Where the band is one vertex wide, each vertex in it has neighbours at the level before and the level after, and touches both pieces. Where the band is two vertices wide, the vertices on its near edge touch the earlier level and those on its far edge touch the later one — and a far-edge vertex need not touch the near piece at all. That is the prediction’s one-sided vertex. But the far edge is always the far edge: every one-sided vertex in a band touches the piece beyond the band, never the piece before it.

The picture shows it on the graph with thirteen one-sided vertices. The band runs from the top of the square down and across to the right; it thickens where it turns, and every red vertex sits on the side facing the green piece. Two one-sided vertices both touch that piece, so the piece connects them; a one-sided vertex and a two-sided one both touch it too. Every pair is joined. Counted over all twenty-four graphs, the one-sided vertices of each separator all touch the same piece, with no exception, and that alone makes every separator a clique. A separator fails the condition only if it has one-sided vertices facing both ways, and a band cut from one breadth-first search cannot: its near edge is the edge the search crossed first, and nothing on that edge can avoid the earlier level.

That is also why the number of spare vertices says nothing about the clique. A separator with thirteen one-sided vertices and one with none are cliques alike; what would break the condition is a single pair of spares facing opposite ways, and the count of such pairs is zero on every graph whatever the count of spares.

The hand-built band of the earlier essay failed for exactly the opposite reason. It was two rows through the middle of a grid, cut from both sides at once: its top row touched only the top piece and its bottom row only the bottom piece. That is the shape a level set never makes.

The order moves the tree, not the factor #

With every separator a clique, the order inside it should change nothing in the factor, and twenty-four shuffles of each confirm it.

The fill is identical across every shuffle of every separator, entry for entry, and so is the work. The critical path moves on one graph of twenty-four, at radius 0.13, by 1.8 per cent, and on none of the others at all. That one movement is real and it is not the factor’s: in the elimination tree each column’s parent is the first later row it has an entry in, so a piece hangs from whichever separator vertex comes first in the chosen order among those it touches. Reorder the clique and a piece’s subtree can hang higher or lower on the separator’s chain, and the longest path from a leaf to the root changes, while every entry of the factor stays where it was. On the other twenty-three graphs every piece touches the chain’s first vertex in every order, or hangs where it does not matter. The prediction’s five per cent was the factor’s to give, and the factor gives nothing.

Trimming is the lever #

The prediction’s last clause holds, more strongly than it was put. A one-sided vertex is in the separator without separating anything: moved into the piece it touches, it leaves the remaining band still a separator, because the piece it joins is the one it was already adjacent to.

Trimming shortens the critical path on nineteen of the twenty-four graphs, by up to 48 per cent — 0.52 of the path remaining on one graph at radius 0.13, 0.54 on the thirteen-vertex graph at 0.11. On five graphs it takes off a third or more. On the four graphs with no one-sided vertex it changes nothing, and on one at 0.16 it lengthens the path by 1.3 per cent: the trimmed separator gives a slightly less balanced dissection there. The best order inside the separator, by comparison, shortens the path by 1.8 per cent on one graph and by nothing elsewhere.

Why so much, for vertices that are a sixth of a separator at most, is arithmetic. The separator is a clique, so its block of the factor is dense and its factorisation costs about a third of the cube of its size, all of it on the critical path, since every leaf’s path to the root runs through the whole separator chain. On the thirteen-spare graph the trim takes the separator from 38 vertices to 25, and the cube’s third from about 18,300 to 5,200: a saving of 13,100 on a path that falls by 24,600 in all. The rest comes from the pieces, whose last columns had rows reaching into the spare vertices and no longer do. A vertex in a dense block costs in proportion to the square of the block’s size; the same vertex in a sparse piece costs in proportion to its few neighbours.

The gain follows the count of spare vertices, roughly: graphs with ten or more give 1.28 to 1.87, graphs with three or fewer give 0.99 to 1.43. It is not proportional — where the spare vertices sit decides how much path they were adding — but no graph with many spares gains little. And the counts run the opposite way to the prediction’s density argument. The sparsest graphs average 5.0 one-sided vertices a separator, the densest 2.4. One reading, not measured here: in a denser graph more of the far edge’s vertices also reach back to the near level, because each has more neighbours, so fewer of them are one-sided; a sparse graph’s level sets are ragged, and the raggedness is the spare vertices.

A dense patch does not fold it #

The prediction’s own picture was of a level crossing a dense region, and uniform graphs do not have one, so the measurement was repeated on graphs that do: 300 points uniform in the square at radius 0.11, plus 64 more in a disc of radius 0.15 at the centre, four times the surrounding density there. Eight seeds. If a level set were ever going to bend back on itself and meet the near piece from the far side — the one shape that could put one-sided vertices on both faces of a band — it would be where the search’s front slows down in a crowd and wraps around it.

It does not happen. On all eight graphs the first separator crosses the disc, with 40 to 78 vertices; it carries three to fourteen one-sided vertices, all of them facing the same piece on every graph; every separator is a clique once its pieces are eliminated; and no shuffle of any of them moves the fill. The breadth-first front does slow in the crowd, and the bands are larger than on the uniform graphs at the same radius — 40 to 78 vertices against 24 to 46 — but slowing makes a band wider without turning it round. A front that wraps a dense patch reaches the far side of the patch from two directions at once, and those two arms belong to the same level and face the same next level.

Trimming on these graphs is a less reliable lever than on the uniform ones. It shortens the critical path by a third on one graph, with fourteen spare vertices, and by 3 to 15 per cent on six; on the seventh, which the separator cut into three pieces, it lengthens the path by a quarter, because the vertices it moves all join one piece and make the dissection lopsided. The depth that is worse than both ends and the halves were the price found balance deciding a dissection’s critical path more than anything inside its separators; a trim that moves vertices only one way can buy back a separator’s slack and spend it on the balance.

What the prediction got right, and wrong #

It was right that level-set separators carry vertices that do not separate, and right that removing them is worth more than ordering them. It was wrong about what those vertices do to the clique, because it treated them as the hand-built band’s top and bottom rows — two-sided failures — when a level set can only make one-sided ones. And it was wrong about density in direction: the dense patch the prediction pictured, where the level crosses many vertices at once, makes a band wider without making it more one-sided, since the vertices in a dense patch reach both levels.

The fill and the work are what most codes measure an ordering by, and on all thirty-two separators measured here, uniform and patched, the separator’s internal order changes neither. The order decides the memory found four orderings of one matrix giving factors a third apart in size; inside a level-set separator there is no such choice to make, and the least fill there is, which searched every order of a small graph, would find every order of a clique tied. The critical path is the one place an internal order can show, through the tree’s shape, and an ordering that buys processors, not time is the account of why that path, and not the work, is what a parallel factorisation waits on.

Pieces ordered blind found that ordering the pieces without the separator in view cost a quarter of the critical path; the halves were the price found the dissection’s balance decided most of the rest. Trimming sits between them: it changes neither the pieces’ order nor the separator’s, only which vertices are in which, and it is worth as much as either on the graphs with the most spares. Eliminating a vertex is a graph operation is the fact under all of this — that elimination joins every pair of a vertex’s neighbours — and the clique condition is that fact applied to a whole piece at once.

What thirty-two graphs do not show #

Every separator here came from one breadth-first search from one peripheral vertex, cut at one level; the argument that its spare vertices face one way depends on exactly that, and a separator built any other way — from a spectral bisection’s sign pattern, from a multilevel partitioner’s refinement, from two fronts meeting — inherits none of it. Only the first separator of a depth-one dissection is measured; deeper levels cut smaller pieces whose own level sets start from different peripheral vertices, and their spare vertices are not counted. The graphs are all 300 to 364 points in a square, so the bands are tens of vertices long and two or three deep; on a mesh with a hundred thousand vertices the same band would be hundreds long and its spares would be numbered in tens, and whether the trim’s share of the critical path holds at that size is the extrapolation this essay does not make. The trim is the simplest one, every one-sided vertex into its piece, with no rebalancing; on the patched graph where it cost a quarter, a trim that moved spares only when the move kept the pieces within ten per cent of each other would presumably have cost nothing, and that is not measured either.

Still open: a patch of high density, and trimming at depth #

Two searches, one separator. A single breadth-first front cannot face both ways, but a separator assembled from two fronts can — the band where a search from the left corner meets a search from the right, as some partitioners build. The prediction with a sign is that on the eight uniform graphs at radius 0.11 such a two-front separator has one-sided vertices on both faces on at least half of them, fails the clique condition there, and that its order moves the fill by more than one per cent — the first separator drawn by an algorithm rather than by hand to do so.

Trimming at every level. A depth-three dissection draws seven separators. The prediction is that trimming each one before its pieces are cut further shortens the critical path by at least as much as trimming the first alone did on the same graph, and on the graphs where the first separator had no spares, by at least ten per cent — because the smaller pieces’ level sets are more ragged than the whole graph’s.