Eliminating a vertex is a graph operation

Gaussian elimination is a numerical procedure that happens to be applied to graphs. It is also, and was first, a graph procedure that happens to be linear algebra: electrical engineers had it in 1899 as the star–mesh transform, and the two are the same operation written twice.

Eliminate vertex v from a Laplacian. The Schur complement’s entry between two of v’s neighbours i and j picks up a term

− (wᵢᵥ · wᵥⱼ) / dᵥ

which is a new edge between i and j with conductance wᵢwⱼ/Σw. Every pair of v’s neighbours gets one. The vertex is gone and its neighbourhood has become a clique.

The class is closed, and that is unusual #

The Schur complement of a Laplacian is a Laplacian. Not approximately: symmetric, zero row sums, every off-diagonal entry nonpositive, at every step of the elimination.

The generator behind the figure checks all three at every step rather than quoting them. Across four graph families and three orderings the worst symmetry and row-sum defect is 3·10⁻¹⁵ relative to the norm, and the count of positive off-diagonal entries is zero at every step of every run.

That closure is worth appreciating because nothing else this site eliminates has it. Eliminating a row of a general sparse matrix produces a matrix that is sparse and is otherwise an arbitrary matrix. Eliminating a row of a symmetric positive definite matrix produces another one, which is more structure than usual and is still just a matrix. Here every intermediate object is a graph, with a picture and an interpretation, and the fill is a set of edges rather than a set of nonzeros.

The interpretation is the electrical one and it is exact: the Schur complement is the network that would be measured from the outside if the eliminated vertices were sealed inside a box. Two networks with the same Schur complement are indistinguishable from their remaining terminals, which is what makes the transform useful and is also why the fill is unavoidable — the box’s behaviour genuinely does couple every pair of terminals.

The ordering, measured #

Five orderings, four graphs, and the number of new edges each produces:

graph          edges   minDegree   natural   reverse   random   maxDegree
grid 36          60        71        125       125      160       293
two blocks 36   184       101        160       169      327       248
preferential     69        31        441        43      245       465
cycle 36         36        33         33        33       33        33
grid 64         112       183        343       343      416       857

The preferential-attachment row is the one to read first: thirty-one edges against four hundred and sixty-five, a factor of fifteen, on the same matrix with the same arithmetic.

The cycle is the counterweight. Every ordering fills 33 edges, because a cycle has no ordering freedom worth having: eliminating any vertex joins its two neighbours, leaving a shorter cycle, and that is the same picture wherever the elimination starts.

On a grid the spread is narrower than fifteen and it widens with the size.

The best ordering is minimum degree at every size and the worst changes. Across grids of 9, 16, 25 and 49 vertices the fill runs 5–17, 18–57, 37–143 and 119–525 — ratios of 3.4, 3.2, 3.9 and 4.4 — with the worst ordering being random at the smallest grid and maximum degree at all three larger ones.

So the factor of fifteen is a property of the preferential-attachment graph and not of orderings. On a grid the same five orderings span between three and four and a half, growing slowly with the size — real, worth having, and an order of magnitude short of what an irregular degree distribution offers. The quantity that decides how much an ordering is worth is therefore the spread of the degrees rather than the size or the density: a cycle has none and gains nothing, a grid has almost none and gains a factor of four, and a preferential-attachment graph has a great deal and gains fifteen.

The transform checked against the formula #

The star–mesh identity is short enough to check by hand, and this field does.

Take a star with four leaves, at conductances 1, 2, 3 and 4, and eliminate the hub. The formula says the leaves are joined pairwise at wᵢwⱼ divided by the total conductance, which is 10 — so the edge between the leaves at 1 and 2 has conductance 0.2, between 2 and 3 it is 0.6, and so on.

Eliminating numerically and comparing every one of the six new conductances against the formula gives a worst discrepancy of 0. Not 10⁻¹⁶: zero, because every quantity involved is a ratio of small integers and every one of them is representable.

That exactness is not general — a star with irrational conductances would not give it — and it is worth having on the one family where it is available, because it separates two questions that are easy to run together. Whether the formula is right is a question about algebra, settled here exactly. Whether the elimination is accurate is a question about arithmetic, settled by the symmetry and row-sum measurements at 10⁻¹⁵. A single test that mixed them would leave both open.

Why minimum degree wins, and where it does not #

The heuristic is one line: eliminate the vertex of lowest current degree, recompute, repeat. It wins on four of the five rows and by a factor of fifteen on the worst one.

The reason is the star–mesh formula. Eliminating a vertex of degree d creates a clique on d vertices, which is d(d − 1)/2 edges, most of them new. So the cost of a step is quadratic in the degree of the vertex removed, and removing low-degree vertices first keeps every step cheap — and, more importantly, keeps the remaining degrees low, because a clique is what raises them.

Maximum degree is therefore the worst possible rule and the table confirms it: on the grid it creates a clique on sixteen vertices at its first step, against six for minimum degree, and pays for it at every step afterwards.

Where minimum degree loses is where a locally cheap choice is globally expensive. The two-block row has maximum degree at 248 against random’s 327, so the “obviously worst” rule beats a random one there — a dense block’s vertices all have similar degrees, so minimum degree has no signal to follow and its advantage narrows. Nested dissection, which orders by a recursive partition rather than by degree, is the rule that wins on structured graphs and it needs the partition machinery from earlier in this field to compute.

The connection to the sparsity field #

This site already has a field about fill: the factor is not sparse measures it on discretisation matrices, and the order decides the memory measures what the ordering is worth there.

What is different here is not the phenomenon but what it is a phenomenon of. In the sparsity field the matrix is the object and the graph is its pattern — a device for reasoning about which entries are nonzero. Here the graph is the object and the matrix is built from it, so the fill is not a statement about a data structure; it is a statement about the network. A fill edge is a genuine conductance between two terminals, present in the physical system and absent from the drawing.

That reversal has a practical consequence. In the sparsity field the numerical values matter — a fill entry that is numerically negligible can be dropped, which is what an incomplete factorisation does. Here dropping one changes the network, and the tree preconditioner two essays along is the systematic version of dropping all of them: keep a spanning tree, which has no fill at all, and pay for the rest in iterations.

What the fill costs, and what it does not #

Fill is a memory statement before it is a time statement, and the two are worth separating.

Memory. Every fill edge is an entry that has to be stored, and the peak is what decides whether an elimination fits. On the grid at 64 vertices the range across orderings is 183 to 857 new edges against 112 original ones, so the choice of ordering decides whether the factor is three times the matrix or nine times it.

Time. The arithmetic is a sum over steps of the square of the degree eliminated, which is more sensitive to the ordering than the fill count is: one clique on sixteen vertices costs 120 updates and one on six costs 15.

Accuracy. Nothing. The elimination of a Laplacian is stable without pivoting — it is symmetric positive semidefinite, so the diagonal dominates and every pivot is positive, which the generator asserts at every step — and the answer is the same to the rounding level whichever ordering is used. That is the pivoting field’s exception rather than its rule: here the ordering is chosen entirely for cost, and stability never enters.

The separation matters because it is unusual. In the general sparse case the ordering trades fill against stability and the threshold between them is a parameter. On a Laplacian there is nothing to trade.

A pivot that is positive but small #

One caveat belongs here, because the assertion in this library nearly missed it.

Every pivot in a connected Laplacian’s elimination is positive, and the generator checks it. The last one is not: the final vertex’s diagonal, after everything else has been eliminated, is mathematically zero, because the whole matrix is singular. In practice it comes out at 10⁻¹⁵ or so, for the reason the grounding essay measured — the row sums are exact and the elimination’s arithmetic is not.

So an elimination of a Laplacian must stop one step early, or ground a vertex first, and a routine that runs to the end divides by a rounding error. The measurement in this field runs to n − 1 steps and asserts positivity on each, which is the correct number and is one fewer than a general elimination performs.

That off-by-one is exactly the kind of thing that produces an answer rather than an error — the last division returns a large number, the back-substitution proceeds, and the result is a vector with an arbitrary constant added to it, which for a potential is the right answer anyway. It is right for the wrong reason, and on a graph where the last pivot rounds to exactly zero it is not right at all.

Fill is not a property of the matrix #

One consequence of the closure is worth stating separately because it is the thing that trips up a sparse-matrix intuition.

In the sparsity field, fill is a property of a matrix and an ordering, and the standard way to reason about it is the elimination tree — a structure computed symbolically, before any arithmetic, that says exactly which entries will fill. The symbolic phase is cheap, exact, and independent of the numerical values.

That is still true here, and it means the whole table above could have been computed without performing a single floating-point operation. The generator performs the elimination numerically anyway, and it does so on purpose: the numerical run is what checks that the Schur complement is still a Laplacian, which is a claim about the values rather than about the pattern. A symbolic run would have produced the same fill counts and would have said nothing about whether the intermediate objects were graphs.

The distinction matters when the elimination is approximate. A symbolic phase can only bound what an approximate elimination will do — what the symbolic phase can only bound is the essay about that — because dropping a small fill entry is a decision about values. On a Laplacian the decision is about conductances, and whether the result is still a graph is exactly the closure property this essay measured.

What this makes possible #

The closure property is not decoration; it is what lets the rest of this anchor exist.

Because every intermediate matrix is a graph, the elimination can be stopped early and what remains is a smaller network with a meaning — which is what a multilevel solver does, and what makes a hierarchy of graphs a sensible object at all. Because the fill has an interpretation, an approximate elimination can drop the weakest new conductances and still be a graph, which is what combinatorial preconditioners do. And because the Schur complement of a Laplacian is a Laplacian, the whole apparatus of this field — effective resistance, conductance, spanning trees — applies to the partially eliminated object as much as to the original.

None of that is available for a general sparse matrix. Its Schur complement is a matrix, its fill has no interpretation, and stopping early leaves an object with no properties beyond the ones a matrix has. The graph field’s advantage over the sparsity field is exactly this closure, and it is why an elimination here can be reasoned about with pictures.

The fill curve, and where it happens #

The figure plots fill against the number of vertices eliminated rather than reporting a total, and the shape is worth reading because it says where the cost is.

Under minimum degree on the grid, twenty-eight of thirty-four steps create at least one fill edge and the largest clique created has six members. The curve rises steadily and never jumps.

Under maximum degree the first step creates a clique on sixteen vertices — a hundred and twenty edges, of which most are new — and the curve leaps immediately and then rises more slowly, because the damage is done and the remaining graph is dense enough that further eliminations add little.

That difference in shape is the operational content. A total of 293 against 71 is a statement about memory; a curve that reaches most of its total in the first two steps is a statement about when the memory is needed, which is what decides whether a factorisation fits at all. A run that allocates incrementally and dies at step two has failed differently from one that dies at step thirty.

It also explains why minimum degree recomputes. The rule looks at the current degrees, after the cliques so far have been added, rather than at the original graph’s degrees — and a static ordering by original degree does much worse, because the first few eliminations change the degrees of everything around them. Recomputing costs a heap operation per step and is what makes the heuristic a heuristic rather than a sort.

What an approximate elimination looks like here #

The last thing worth saying is what happens when the fill is not accepted, because it sets up the two essays after this one.

Three responses to a fill count of 465, in increasing order of how much they give up.

Reorder. Free, exact, and worth a factor of fifteen on the graph above. Nothing about the answer changes. This is the whole content of the ordering literature and it is the first thing to try.

Drop the small fill. Keep the elimination but discard new conductances below a threshold. The result is no longer a factorisation of the original — it is an incomplete one — and what it is good for is preconditioning rather than solving. On a Laplacian the dropped quantities are conductances, so the incomplete factor is still a graph and the closure property survives the approximation.

Drop all of it. Keep a spanning tree, which has no fill by construction: eliminating a leaf of a tree creates no clique, because a leaf has one neighbour. A tree can be eliminated in linear time with zero fill, and the whole cost has been moved into the iteration count of whatever uses it as a preconditioner. A preconditioner that is a tree measures what that costs, and the answer is a number with no arithmetic in it.

Those three are the same trade at three settings, and the graph reading is what makes the third one even thinkable. On a general sparse matrix “keep a spanning tree of the pattern” is not a meaningful instruction; here it is a subgraph, it has a Laplacian, and its quality can be scored before anything is factorised.

The three on one table #

Listing them in increasing order of what they give up is an ordering of concessions, and it is easy to read it as an ordering of value. They can be priced against each other in one currency: how many off-diagonal entries the preconditioner stores, and what κ of the preconditioned system comes out at.

Grounded grid Laplacians, incomplete Cholesky at a drop threshold τ, against a BFS spanning tree:

τ = 0 is the direct method and κ is exactly 1, which is the control the table needs: the incomplete family degenerates to the complete factorisation at one end, so this is one curve rather than three techniques.

The tree degrades more slowly with the problem than a fixed-threshold factor does. Fitted against n, κ grows as n^1.69 at τ = 0.1 and as n^1.18 for the tree. Different exponents mean the curves cross, and they have crossed by the bottom of this table: at 7×7 the aggressive incomplete factor stores 82 entries for κ = 225 while the tree stores 48 for κ = 102 — fewer entries and better conditioning, on both axes at once.

That is a domination rather than a trade, and it is exactly what an ordering by concession conceals. Dropping small fill is the right move at a mild threshold, where nothing else comes close — at τ = 0.1 on the 7×7 it keeps 40% of the complete factor’s entries for κ = 27, and no tree of any kind reaches that. At an aggressive threshold it is strictly worse than the option that supposedly gives up more. The three responses are not three points on a frontier; the second one leaves the frontier partway along.

The mechanism is the graph reading again. A tree is chosen for its structure — every vertex reachable, no cycles, a stretch that can be bounded before anything is factorised — while a drop threshold selects by magnitude and has no view of the graph at all. Past a point, discarding by magnitude disconnects what matters and keeps what does not, and the ordering of concessions is silent about which of those a given threshold is doing.

assertTheMiddleResponseIsDominated measures the whole table, fits both exponents, and requires the tree to beat the aggressive factor on both axes at the largest grid — while also requiring the mild threshold to beat every tree, since the middle response is right where it is right.