Numerical Linear Algebra
where the algebra stops being the arithmetic
The matrix that is a graph

Eliminating a vertex is a graph operation

Gaussian elimination on a Laplacian deletes a vertex and joins its neighbours into a clique with conductances wᵢwⱼ over Σw. The matrix that remains is still a graph — symmetric, zero row sums, nonpositive off the diagonal — and the ordering decides whether the fill is thirty-one edges or four hundred and sixty-five.
31 min read 25 figures Where the algebra stops being the arithmeticIdentical algebra, different arithmeticMeasured, not asserted

Worth reading first: A matrix with no numbers in it · Elimination is a sequence of choices · The factor is not sparse.

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.

Same matrix, same arithmetic, 4.13× the fillGaussian elimination on the Laplacian of the grid 6×6, under five orderings, counting the edges that did not exist before. Eliminating a vertex removes it and joins its neighbours into a clique — the star–mesh transform, which is what the Schur complement of a Laplacian does — so fill is a set of edges rather than a set of nonzeros, and the matrix that remains is still a graph: symmetric, zero row sums, nonpositive off the diagonal, checked at every step and worst at 3·10⁻¹⁵. Minimum degree fills 71 edges against 293 for the worst ordering here, on a graph with 60 to start with. Nothing about the arithmetic differs between these five runs.05101520253035059118177236295vertices eliminatededges of fill so farminDegree: 71natural: 125reverse: 125random: 160maxDegree: 293fill, by orderingminDegree71natural125reverse125random160maxDegree293edges to start60eliminating a vertex makes a cliqueand the order decides how big
Fig. 1 Five orderings of the same thirty-six-vertex grid, counting the edges that did not exist before. Nothing about the arithmetic differs between the runs.

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.

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.

Same matrix, same arithmetic, 15× the fillGaussian elimination on the Laplacian of the preferential 36, under five orderings, counting the edges that did not exist before. Eliminating a vertex removes it and joins its neighbours into a clique — the star–mesh transform, which is what the Schur complement of a Laplacian does — so fill is a set of edges rather than a set of nonzeros, and the matrix that remains is still a graph: symmetric, zero row sums, nonpositive off the diagonal, checked at every step and worst at 2.86·10⁻¹⁵. Minimum degree fills 31 edges against 465 for the worst ordering here, on a graph with 69 to start with. Nothing about the arithmetic differs between these five runs.05101520253035093186279372465vertices eliminatededges of fill so farminDegree: 31natural: 441reverse: 43random: 245maxDegree: 465fill, by orderingminDegree31natural441reverse43random245maxDegree465edges to start69eliminating a vertex makes a cliqueand the order decides how big
Fig. 2 A preferential-attachment graph, where minimum degree fills thirty-one edges and maximum degree fills four hundred and sixty-five.

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. The next essay but one 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.

At other settings

Same matrix, same arithmetic, 3.17× the fillGaussian elimination on the Laplacian of the grid 4×4, under five orderings, counting the edges that did not exist before. Eliminating a vertex removes it and joins its neighbours into a clique — the star–mesh transform, which is what the Schur complement of a Laplacian does — so fill is a set of edges rather than a set of nonzeros, and the matrix that remains is still a graph: symmetric, zero row sums, nonpositive off the diagonal, checked at every step and worst at 1.17·10⁻¹⁵. Minimum degree fills 18 edges against 57 for the worst ordering here, on a graph with 24 to start with. Nothing about the arithmetic differs between these five runs.024681012141601122334455vertices eliminatededges of fill so farminDegree: 18natural: 27reverse: 27random: 32maxDegree: 57fill, by orderingminDegree18natural27reverse27random32maxDegree57edges to start24eliminating a vertex makes a cliqueand the order decides how big
Fig. 3 A smaller grid, where the orderings are still separated by a factor of three.
Same matrix, same arithmetic, 4.68× the fillGaussian elimination on the Laplacian of the grid 8×8, under five orderings, counting the edges that did not exist before. Eliminating a vertex removes it and joins its neighbours into a clique — the star–mesh transform, which is what the Schur complement of a Laplacian does — so fill is a set of edges rather than a set of nonzeros, and the matrix that remains is still a graph: symmetric, zero row sums, nonpositive off the diagonal, checked at every step and worst at 2.77·10⁻¹⁵. Minimum degree fills 183 edges against 857 for the worst ordering here, on a graph with 112 to start with. Nothing about the arithmetic differs between these five runs.091827364554630171342513684855vertices eliminatededges of fill so farminDegree: 183natural: 343reverse: 343random: 416maxDegree: 857fill, by orderingminDegree183natural343reverse343random416maxDegree857edges to start112eliminating a vertex makes a cliqueand the order decides how big
Fig. 4 A larger one, where the gap has widened to four and a half.
Same matrix, same arithmetic, 3.24× the fillGaussian elimination on the Laplacian of the two blocks 36, under five orderings, counting the edges that did not exist before. Eliminating a vertex removes it and joins its neighbours into a clique — the star–mesh transform, which is what the Schur complement of a Laplacian does — so fill is a set of edges rather than a set of nonzeros, and the matrix that remains is still a graph: symmetric, zero row sums, nonpositive off the diagonal, checked at every step and worst at 2.25·10⁻¹⁵. Minimum degree fills 101 edges against 327 for the worst ordering here, on a graph with 184 to start with. Nothing about the arithmetic differs between these five runs.05101520253035065130195260325vertices eliminatededges of fill so farminDegree: 101natural: 160reverse: 169random: 327maxDegree: 248fill, by orderingminDegree101natural160reverse169random327maxDegree248edges to start184eliminating a vertex makes a cliqueand the order decides how big
Fig. 5 Two blocks, where minimum degree has less signal to follow.
Same matrix, same arithmetic, 1× the fillGaussian elimination on the Laplacian of the cycle 36, under five orderings, counting the edges that did not exist before. Eliminating a vertex removes it and joins its neighbours into a clique — the star–mesh transform, which is what the Schur complement of a Laplacian does — so fill is a set of edges rather than a set of nonzeros, and the matrix that remains is still a graph: symmetric, zero row sums, nonpositive off the diagonal, checked at every step and worst at 4.06·10⁻¹⁶. Minimum degree fills 33 edges against 33 for the worst ordering here, on a graph with 36 to start with. Nothing about the arithmetic differs between these five runs.051015202530350714212835vertices eliminatededges of fill so farminDegree: 33natural: 33reverse: 33random: 33maxDegree: 33fill, by orderingminDegree33natural33reverse33random33maxDegree33edges to start36eliminating a vertex makes a cliqueand the order decides how big
Fig. 6 A cycle, where every ordering fills the same thirty-three edges.
preferential 60: 60 vertices, 117 edges, and a matrix built from themThe preferential 60 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 0.5861 and the largest computed zero is 4.82·10⁻¹⁷, a gap of 1.22·10¹⁶. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 248.the matrix, measuredvertices60edges117‖L·1‖∞0zero eigenvalues1components, by search1λ₂0.59laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 7 The degree-skewed graph on which the orderings differ by a factor of fifteen.
grid 6×6: 36 vertices, 60 edges, and a matrix built from themThe grid 6×6 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 0.2679 and the largest computed zero is 2.36·10⁻¹⁶, a gap of 1.13·10¹⁵. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 120.the matrix, measuredvertices36edges60‖L·1‖∞0zero eigenvalues1components, by search1λ₂0.27laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 8 The grid the hero figure eliminates.
κ is between 1 and the total stretch, and the bound is 2.28–3.47× looseThree spanning trees of the grid 5×5 used as preconditioners. For each, the bar spans the smallest and largest eigenvalue of L_T⁻¹L_G on the subspace orthogonal to the constant vector, and the tick is the total stretch — the sum over the graph's edges of the resistance of the path the tree makes them take, which is an integer for an unweighted graph and contains no arithmetic at all. The smallest eigenvalue is 1 to 2·10⁻¹⁵ on every tree, which is a theorem rather than a measurement: a tree is a subgraph, so its quadratic form is never the larger. The largest is below the stretch on every tree, by between 2.28 and 3.47. Choosing a preconditioner is therefore choosing a tree, and it can be scored without factorising anything.10⁻¹110¹10²10³1234eigenvalue of the preconditioned Laplacian, and the stretchbreadth-firstκ = 34.62randomκ = 55.17random, secondκ = 37.11the bar is the spectrumthe tick is a combinatorial bound
Fig. 9 The elimination with all of its fill dropped, scored combinatorially.
Backward stable at every size, and wrong from n = 16The number of spanning trees of the complete graph on n vertices, by Kirchhoff's theorem: the determinant of the Laplacian with one row and column deleted, which is nⁿ⁻² by Cayley's formula and is therefore a whole number known in advance. It is computed twice — in BigInt rationals, where the answer is exact, and by the site's own pivoted elimination in binary64. The filled curve is the relative error of the elimination, which never leaves the rounding level: worst 9.38·10⁻¹⁵ across the whole range, so the algorithm is backward stable at every size. The dashed curve is the spacing between consecutive doubles at the answer's own magnitude, relative to the answer. Where they cross, at n = 16, the count has 17 digits and a binary64 has sixteen: rounding to the nearest integer cannot recover it, because the nearest two representable numbers there are 8 apart. The error is committed by the format and not by the elimination, which is a distinction no residual can make.57911131517192110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹vertices of the complete graphrelative sizethe algorithm is not the problemsizes counted18worst relative error9.4·10⁻¹⁵first wrong at n =16digits in the answer17spacing of doubles there8largest integer a double holds9·10¹⁵the elimination stays at the rounding levelthe format runs out
Fig. 10 What the same elimination’s determinant counts.
Fill growth under reverse Cuthill–McKee: the factor rises as n^1.41A log-log plot of nonzero count against matrix dimension. The matrix's own count is a straight line of slope one; the factor's is steeper; a dense factor is steeper still.10²10².³10²10³10⁴n (dimension)nonzerosdense factorfactor, n^1.41matrix, n^1.05grid Laplacians from 5×5 to 12×12fitted, not quoted
Fig. 11 Fill in the sparsity field, where the graph is a pattern rather than the object.
What one symmetric permutation does to the storage, on a matrix it does not changeThe same 256 × 256 matrix, its rows and columns renumbered by one permutation and its columns by the same one. The condition number is 24.3948 either way, to eight digits; the Frobenius norm is 6139.964 either way, to twelve. Nothing a norm can see has moved. Clustered, the partition stores 27,008 numbers. Shuffled, the admissibility test finds no admissible pair anywhere — every cluster of a shuffled numbering spans the whole interval, so every q is infinite — and the format degenerates to dense storage exactly. The rule with no test to fail does worse than that: it compresses every off-diagonal block regardless, gets ranks up to 119 out of 128, and stores 118,208 numbers — 1.80 times the matrix it was compressing. A rank-119 factorisation of a 128-column block is a more expensive way to write down the block than the block.numbers stored, 256 × 256clustered, strong27,008clustered, weak24,064the dense matrix65,536shuffled, strong65,536shuffled, weak118,208the same matrix, twiceκ, clustered24κ, shuffled24‖A‖_F, clustered6140‖A‖_F, shuffled6140shuffled weak ⁄ dense1.8the compressibility is in the numberingand the numbering is not in the matrix
Fig. 12 What the ordering is worth in memory, in the field that measured it first.
One system, 36 ways to remove its kernel, and 2.85× between themA Laplacian is singular, so a solve has to remove its kernel, and the usual way is to delete one row and column — grounding a vertex, in the electrical reading. Which vertex is a free parameter that no account of the method mentions, and it is set by whichever index the code happens to drop. Every point here is one choice on the grid 6×6: the condition number of the resulting positive definite matrix against the degree of the vertex removed. Grounding vertex 5, of degree 2, gives κ = 275.34; grounding vertex 15, of degree 4, gives 96.565 — a factor of 2.851 between two ways of solving the identical problem. The trend is that a high-degree vertex is the better ground, which has a reading: grounding a vertex fixes its potential, and fixing the potential of something the rest of the graph is strongly attached to constrains more of the graph.23410²degree of the grounded vertexcondition number of what is left96.56, the best choicea parameter nobody setsvertices tried36best κ97at degree4worst κ275at degree2spread2.9one row and column deletedand it matters which
Fig. 13 The vertex that is not eliminated, and what choosing it costs.
Twenty eigenvalues, one of them zero, and the graph has one pieceThe Laplacian spectrum of two ten-vertex paths joined by a single edge of conductance 1, plotted on a logarithmic axis so the zero end is visible. The dashed line is the threshold 10⁻¹⁰‖L‖ = 1.06·10⁻⁹, and the number of eigenvalues below it is the spectral count of connected components: 1. Breadth-first search, which performs no arithmetic on any weight, says 1. The largest computed zero is 5.81·10⁻¹⁷ and the smallest eigenvalue above the threshold is 0.02462. A count of components is therefore a rank decision at a threshold, and the bridge's conductance decides which side of it λ₂ falls on — at nine orders above the rounding level, not at it.13579111315171910⁻¹⁹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹indexeigenvalue of L10⁻¹⁰‖L‖, the thresholda count that is a thresholdeigenvalues below it1components, by search1largest computed zero5.8·10⁻¹⁷smallest above it0.025ratio4.2·10¹⁴the graph is connectedat every stop of the slider
Fig. 14 The zero eigenvalue that makes the last pivot vanish.
Resistance to 15 vertices, against an answer that is a ratio of integersEffective resistance from vertex 0 to every other vertex of the grid 4×4, computed twice in floating point — once by grounding a vertex and eliminating, once by summing (uₖᵢ − uₖⱼ)²/λₖ over the whole spectrum — and once in BigInt rationals, where for an unweighted graph the answer is exactly a ratio of two integers and there is no rounding anywhere. The curves are the relative errors of the two floating-point routes against that exact answer: at worst 4.75·10⁻¹⁶ for the elimination and 9.98·10⁻¹⁶ for the spectral sum, which use no arithmetic in common beyond the matrix they are both handed. Foster's theorem says Σ w·R over the edges is exactly n − 1 whatever the graph is; it comes to 15 against 15.1357911131510⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1vertexrelative error against the exact answerthree routes, one numberworst, by elimination4.8·10⁻¹⁶worst, by spectrum10·10⁻¹⁶solve residual1.5·10⁻¹⁵Foster's sum15n − 115difference3.6·10⁻¹⁵the answer is a ratio of integersso the error is known
Fig. 15 The quantity a partially eliminated network still has, because the class is closed.
Growth factor under partial pivoting to n = 40: the bound, the worst case, and realityGrowth factor against matrix size on a logarithmic vertical axis. The two-to-the-n bound rises as a straight line; Wilkinson's matrix sits exactly on it; random matrices stay near one.0816243240110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴matrix size ngrowth factor max|u| / max|a|the 2ⁿ⁻¹ boundworst of 30 randommedian randomWilkinson's matrix sits on the bound30 Gaussian matrices per sizeat n = 40: bound 5.5·10¹¹, worst 4.8
Fig. 16 Growth under elimination, which a Laplacian has none of.
Elimination with and without pivoting, ε = 10⁻¹²The same two-by-two system solved twice. With a row swap the answer is exact; without one the upper triangular factor contains an entry of order one over epsilon and the second component of the answer is wrong.[ ε 1 ; 1 1 ] x = [ 1 ; 2 ], exact answer (1.000000, 1.000000)with partial pivoting1101U after elimination1.0000001.000000computed xbackward error 0forward error 0without10⁻¹²10-10·10¹¹U after elimination0.9999781.000000computed xbackward error 5.5·10⁻⁶forward error 1.6·10⁻⁵no error is raisedgrowth 10·10¹¹
Fig. 17 An elimination without a pivot rule, in the field where one is needed.
What each way of eliminating a constraint inherits, over five decades of κ(A)The same system solved twice, at 8 unknowns and 3 constraints with κ(H) = 100. The range-space method forms S = AH⁻¹Aᵀ and inherits κ(S), which rises from 12.99 to 3.981·10¹⁰ — the square of κ(A), for the reason the normal equations square it. The null-space method solves with the reduced Hessian ZᵀHZ, whose condition number is 21.13 at the start of the sweep and 21.13 at the end: it does not contain κ(A) at all. The two forward errors, measured against a solution computed in BigInt rationals, follow their own condition numbers: 5.314·10⁻⁶ against 5.788·10⁻¹² at the far end. Both methods are correct and one of them is usable.01234510⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹log₁₀ κ(A)condition number, and relative errorκ(S)κ(ZᵀHZ)range-space errornull-space erroragainst a BigInt answerκ(S) at κ(A) = 10⁵4·10¹⁰κ(ZᵀHZ), all stops21range-space forward error5.3·10⁻⁶null-space forward error5.8·10⁻¹²both are the same algebraand only one squares
Fig. 18 Two eliminations of one problem, differing in their arithmetic rather than their order.
Backward and forward error against the condition numberA log–log plot over twelve decades of condition number. The backward error is a flat line at ten to the minus sixteen; the forward error rises in proportion to the condition number.110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method
Fig. 19 The two errors, neither of which the ordering here moves.
The exact solution of a 13×13 Hilbert system beside the computed oneTwo columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.H13 x = b, b formed exactly so that x = (1, 2, …, 13)12345678910111213exact1.00002.00003.00133.97865.18864.993010.46720.048921.2657-2.575319.21478.906013.5113computed6.6 correct digits4.8 correct digits3.4 correct digits2.3 correct digits1.4 correct digit0.8 correct digitno correct digitsno correct digitsno correct digitsno correct digitsno correct digits0.6 correct digit1.4 correct digitbackward error2.2·10⁻¹⁷κ = 1.7·10¹⁸The algorithm solved a neighbouring problem perfectly. That problem's answer is this one.right-hand side built in BigInt rationalsthe truth is known
Fig. 20 An answer that is known, which the next essay’s determinant also has.
How much a perturbation of the right-hand side is amplified, κ = 10⁶The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ
Fig. 21 The amplifier belonging to the problem, which the ordering does not change.
Backward error, forward error and the condition number, with measured valuesTwo boxes at the top — the problem posed and the nearby problem the algorithm answered exactly — and two answers below them, with the distances between all four labelled by numbers from a Hilbert solve.the problem you posedA = H10b = A·(1, 2, …, 10)the problem it answered exactlyA + δA, b + δb‖δ‖ / ‖A‖ = 2.3·10⁻¹⁷the answer you wantedx = (1, 2, …, 10), exactlythe answer you gotx̂, wrong by 2.7·10⁻⁴ relativebackward error 2.3·10⁻¹⁷forward error 2.7·10⁻⁴κ = 1.6·10¹³κ · η = 3.6·10⁻⁴, and the measured forward error is 2.7·10⁻⁴.The algorithm is not at fault. The problem is.H10, LU with partial pivotingresidual and error differ
Fig. 22 The identity every measurement here is read against.
Forward error of a 6×6 Hilbert solve at eight precisionsA bar for each significand width from 12 to 53 bits showing the relative error in the computed solution, with the condition number times the unit roundoff marked as a prediction.κ = 1.5·10⁷ · the exact answer is (1, 2, …, 6)12 bits3.316 bits0.8620 bits4.324 bits0.09330 bits7.6·10⁻⁴36 bits6.2·10⁻⁶43 bits2·10⁻⁷53 bits4.5·10⁻¹¹dashed: κ · unit roundoffone matrix, eight arithmeticsmeasured against a known answer
Fig. 23 The precision knob, which changes nothing about a fill count.
The 12×12 grid Laplacian and its Cholesky factor, ordered by naturalTwo square sparsity plots side by side. The left shows the nonzeros of the matrix; the right shows the nonzeros of its Cholesky factor, with the entries created by elimination marked in a second colour.the matrix, lower triangle408 entriesits Cholesky factor1739 entries · 1331 created→‖A − LLᵀ‖/‖A‖1.4·10⁻¹⁶fill, symbolic1331fill, numeric1331n = 144 · density 3.2% · bandwidth 12same matrix, renumberedthe answer is identical to rounding
Fig. 24 A sparsity pattern before and after, in the field that draws them.
The lower bound is attained and the upper one is out by 37.3×Cheeger's inequality on nine graphs of about 40 vertices each: for the normalised Laplacian's λ₂, λ₂/2 ≤ φ ≤ √(2λ₂), where φ is the conductance the sweep cut actually achieves. Each row shows the two bounds as a bar and the measured conductance as a dot inside it. The lower bound is tight on the complete at a ratio of 1. The upper bound is loosest on the barbell — by a factor of 37.3 — which is the graph in the census with a real bottleneck, and therefore the shape the inequality is always quoted about. The square root is what makes it loose: it is the price of turning a spectral quantity into a combinatorial guarantee, and it is paid where the guarantee is wanted.10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph
Fig. 25 The partition an ordering by dissection would be built from.

Where this goes next

the matrix, lower triangle408 entriesits Cholesky factor1739 entries · 1331 created→‖A − LLᵀ‖/‖A‖1.4·10⁻¹⁶fill, symbolic1331fill, numeric1331n = 144 · density 3.2% · bandwidth 12same matrix, renumberedthe answer is identical to rounding The factor is not sparse A sparse matrix has a factor that is not sparse, and the gap between them is the entire reason iterative methods exist. The entries elimination creates can be counted before any arithmetic runs, from the graph alone. natural1739reverse Cuthill–McKee1354minimum degree1026nested dissection1413matrix: 408 entries · dense factor: 10440bandwidth 12 · 4.26× the matrixbandwidth 12 · 3.32× the matrixbandwidth 123 · 2.51× the matrixbandwidth 108 · 3.46× the matrixn = 144, five-point stencilevery ordering fills in; none avoids it The order decides the memory Four elimination orderings on one matrix give factors of 1,739, 1,354, 1,413 and 1,026 entries. All four factorisations are exact, all four return the same answer, and the one with the better asymptotics is not the one that wins. 10⁻¹110¹10²10³1234eigenvalue of the preconditioned Laplacian, and the stretchbreadth-firstκ = 34.62randomκ = 55.17random, secondκ = 37.11the bar is the spectrumthe tick is a combinatorial bound A preconditioner that is a tree Every eigenvalue of a tree-preconditioned Laplacian is at least one and at most the total stretch — a combinatorial integer with no arithmetic in it. Measured, the bound is two to four times loose, and on a grid the preconditioner makes the conditioning worse by a factor of 1.85 at every size.

What links here

Computed from the collection, not written here: the essays that point at this one.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Combinatorial preconditioningFillGraph eliminationGraph laplacianMinimum degreeOrderingSchur complementSparsity patternStar mesh transformStretch