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

A distance computed by a solve

Effective resistance is the one quantity in this field with no combinatorial route to it — it is defined by a linear system. On a small unweighted graph the answer is a ratio of two integers, so for once the error is known rather than estimated, and every resistance in a graph has to add up to a number fixed in advance.
31 min read 27 figures Where the algebra stops being the arithmeticTwo routes to a numberExact ground truthMeasured, not asserted

Worth reading first: A matrix with no numbers in it · The vertex nobody solves for · An answer that is known.

Everything the graph field has measured so far had a combinatorial route to it. A component count can be got by breadth-first search, a conductance by counting edges, a partition by enumeration on a small enough graph. The spectral route was one of two, and having two was the point.

Effective resistance has no second route of that kind. It is defined by a linear system:

R(i, j)  =  (eᵢ − eⱼ)ᵀ L⁺ (eᵢ − eⱼ)

where L⁺ is the pseudoinverse of the Laplacian. There is no way to read it off the edge list, no counting argument that produces it, and no shortest path that approximates it. It is the potential difference when one ampere is injected at i and drawn out at j, and computing it means solving.

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. 1 Effective resistance from one vertex of a four-by-four grid to every other, computed three ways: by grounding and eliminating, by summing over the spectrum, and in BigInt rationals where the answer is exact.

Three routes, and the third one is exact

The absence of a combinatorial route makes the site’s habit harder and more valuable, so the field supplies three.

The grounded elimination. Delete one row and column of L, solve, read the potential difference. One factorisation serves every pair, since the inverse of the grounded matrix is what all of them are read from.

The spectral sum. R(i,j) = Σ over the non-zero modes of (uₖᵢ − uₖⱼ)²/λₖ. This uses the entire eigendecomposition, where the first route uses none of it, so the two share no arithmetic beyond the matrix they were both handed.

BigInt rationals. For an unweighted graph the Laplacian has integer entries, so the grounded system can be solved exactly in rationals and the answer is a ratio of two integers with no rounding anywhere.

The first row of the four-by-four grid, exactly:

0   157/224   263/224   181/112   157/224   97/112   8/7   327/224   ...

Against those, the elimination is right to 2.7·10⁻¹⁵ at worst and the spectral sum to a comparable level, with the solve’s own relative residual at 1.5·10⁻¹⁵.

That is the site’s strongest form of ground truth since the Hilbert inverse: the error is known rather than bounded, because one of the routes has none.

And there is an identity that fixes the total

Foster’s theorem is the reason this field’s resistances can be checked without a second routine at all. For any connected graph,

Σ over edges of  w(e) · R(e)  =  n − 1

exactly, whatever the graph is. Not asymptotically, not up to a constant: the weighted resistances of the edges of an n-vertex graph sum to n − 1.

Measured across seven families:

graph               Foster's sum        n − 1     error
path 20             19.000000000000       19      0
cycle 17            16.000000000000       16      0
grid 5×6            29.000000000000       29      3.6·10⁻¹⁵
barbell 7           13.000000000000       13      1.1·10⁻¹⁴
two blocks 40       39.000000000000       39      3.6·10⁻¹⁴
preferential 40     39.000000000000       39      7.1·10⁻¹⁵
hypercube 4         15.000000000000       15      0

Three of the seven are exact — the path, the cycle and the hypercube, whose resistances happen to be representable — and the rest are at the rounding level.

This is a check of a kind this site has very few of. A comparison against a second routine tests whether two implementations agree; an identity like Foster’s tests whether the answer is right, against a number nobody computed. It is available on every graph, at the cost of one pass over the edges once the resistances are known, and it would catch a systematic error that both floating-point routes made together.

Why the identity is the check worth having

It is worth dwelling on Foster’s theorem, because it is a rarer kind of test than it looks and this site has been explicit about the difference.

Most verification in numerical work is comparative: run two implementations, or one implementation at two precisions, and check that they agree. That is a real test and it has a known blind spot — two routes that share a mistake agree perfectly. The site’s two routes to a number thread is built to avoid that by choosing routes with as little shared arithmetic as possible, and the two floating-point routes here are chosen that way.

Foster’s identity is a different kind of test. It compares the computed answer against a number derived from nothing but the graph’s vertex count, so no error in any implementation can satisfy it by accident. A routine that computed every resistance twice as large would agree with itself and fail Foster by a factor of two. One that dropped a term in the spectral sum would agree with nothing and fail Foster. One that grounded the wrong vertex would still pass, correctly, because the resistance does not depend on the grounding — and the identity is not supposed to catch that, because there is nothing there to catch.

The site has three checks of this class and it is worth listing them together: the Hilbert matrix’s closed-form inverse, Kirchhoff’s theorem returning an integer, and this. Each compares a computation against a mathematical fact rather than against another computation, and each is available only because the object has enough structure to have one.

What the quantity is

Three properties make it useful, and the third is the one the next essay depends on.

It is a metric. R(i,k) ≤ R(i,j) + R(j,k), checked here on the four-by-four grid over several triples. So it is a genuine distance on the vertices, unlike the shortest-path distance in one important respect: it takes account of how many paths there are rather than only the shortest.

It is smaller than the hop distance, and by how much says something. On the grid the ratio of resistance to hop count runs from 0.31 to 0.70; on a cycle from 0.50 to 0.92; on the complete graph it is exactly 0.20 for every pair. Two vertices joined by many short paths have a resistance far below their hop distance; two joined by one path have resistance equal to it. On a path graph the resistance between two vertices is exactly the number of edges between them — the exact rational route returns the integer — because there is only one way to get there.

And it has closed forms on the families with symmetry. On the complete graph R(i,j) = 2/n for every pair, returned exactly as 2/5, 1/4 and 1/6 at n = 5, 8 and 12. On the cycle R(i,j) = d(n − d)/n where d is the hop distance, checked at three separations on a twelve-cycle. Those closed forms are what the assertions in this field are calibrated against, rather than against a plausible-looking number.

Why the pseudoinverse is not formed

The definition names L⁺ and no implementation computes it.

Forming a pseudoinverse means an eigendecomposition or an SVD, which is cubic and dense, on a matrix that was sparse. Every entry of the result is nonzero even when L has three per row. And the quantity actually wanted is a handful of quadratic forms in it, not the matrix.

The grounded route gets them from one factorisation of an (n − 1) × (n − 1) matrix that inherits L’s sparsity, which is the same trade the inverse essays make in the elimination field: an inverse appears in the formula and a solve appears in the code, and the two are the same answer at different costs.

The grounding introduces the free parameter an earlier essay measured — which vertex to delete, worth up to nine hundred in the conditioning — and the resistance itself is independent of it, because the potential difference between two vertices does not depend on where the potential was pinned. That independence is worth checking rather than assuming, and it is: computing the same resistance with different vertices grounded agrees at the rounding level.

Resistance to 15 vertices, against an answer that is a ratio of integersEffective resistance from vertex 0 to every other vertex of the cycle 16, 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 3.64·10⁻¹⁶ for the elimination and 1.07·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 elimination3.6·10⁻¹⁶worst, by spectrum1.1·10⁻¹⁵solve residual1.4·10⁻¹⁵Foster's sum15n − 115difference1.8·10⁻¹⁵the answer is a ratio of integersso the error is known
Fig. 2 The cycle, where the resistance has a closed form and the exact route returns it as a ratio of integers.

What the spectral route is for

Given that the elimination is faster and no less accurate, the spectral sum looks like a check and nothing more. It is also the form in which the quantity is understood.

Written as a sum over modes, R(i,j) = Σ (uₖᵢ − uₖⱼ)²/λₖ, the small eigenvalues dominate. A pair of vertices separated by a bottleneck has a large component in the low modes — those are the modes that distinguish the two sides — and each such component is divided by a small λ. So a large effective resistance means a bottleneck, and the connection between resistance and the conductance essays is not an analogy: it is the same eigenvalues, weighted differently.

That is also why resistance is the right sampling probability for a spectral sparsifier. An edge with high effective resistance is an edge the graph’s low modes depend on, and losing it changes the quadratic form; an edge with low resistance is one of many parallel routes and can be replaced by its neighbours. Sampling in proportion to resistance is sampling in proportion to how much of the spectrum an edge carries, and Foster’s identity is what makes those probabilities sum to something known.

Where it is used, and why the definition looks odd until then

A quantity defined by a solve invites the question of what it is for, and the answer is that it turns up in four places where nothing simpler works.

Sampling. The next essay’s sparsifier keeps each edge with probability proportional to its effective resistance, and the resulting graph preserves every quadratic form. No other sampling probability is known to do that.

Clustering and embedding. The resistance metric is a genuine distance that takes account of the number of paths rather than the shortest one, which is what makes it useful where a hop distance is not — two vertices joined by one long path and two joined by twenty short ones can have the same hop distance and resistances differing by a factor of twenty.

Network reliability. The resistance of an edge is exactly the probability that the edge appears in a uniformly random spanning tree, which connects it to the counting essay three along and gives Foster’s identity its combinatorial reading: the expected number of edges in a spanning tree is n − 1, because every spanning tree has n − 1 edges.

And solver design. A preconditioner built from a subgraph is scored by a sum of resistances, which is the quantity the tree essay calls stretch.

That last reading is the one that makes Foster’s theorem feel less like a coincidence. Σ w·R(e) = n − 1 says the resistances of the edges are a probability distribution scaled by n − 1, and the distribution is the one a random spanning tree induces. An identity with a probabilistic proof is a better thing to check a computation against than an identity with only an algebraic one, because it comes with an interpretation of what a violation would mean.

What it costs

The exact route is the expensive one and it is worth being precise about how expensive.

BigInt rationals grow: the numerators and denominators of the entries of an exactly inverted integer matrix are integers of length proportional to the size, so the arithmetic is superquadratic in the dimension on top of the cubic elimination. In practice the route is affordable to about two dozen vertices, which is why this field’s figures cap it there and refuse beyond it.

That cap is the reason the exact route appears in one figure rather than in all of them. Everywhere else the check is Foster’s identity, which costs nothing and is available at every size — and the existence of the exact route on small graphs is what says Foster’s identity is being checked against the right thing.

The floating-point routes are ordinary: one elimination of an (n − 1) × (n − 1) sparse symmetric positive definite matrix, or one eigendecomposition. For all-pairs resistances the elimination is solved n − 1 times against unit vectors, which is a dense inverse in disguise; for a handful of pairs it is one factorisation and a few solves.

Where the accuracy actually goes

One measurement is worth recording because it did not go the way the shape of the problem suggests.

The relative error of both floating-point routes against the exact answer stays at 10⁻¹⁵ across every family and size tried. It does not grow with n, and it does not grow with the graph’s conditioning in any visible way.

The reason is that a Laplacian’s grounded submatrix is well conditioned on these families — κ between about 100 and 1,400 — and pivoted elimination on a well-conditioned symmetric positive definite matrix is as good as arithmetic gets. The error identity predicts a forward error of about κ times the unit roundoff, which is 10⁻¹³ at worst, and the measurement comes in two orders below that.

So the difficulty in this quantity is not numerical. It is that the quantity is defined by a solve and therefore costs a solve, on an object whose other properties are all available by counting — and the essays that follow are about what that buys.

What a disconnected graph does to it

The refusal this essay is checked by is worth explaining, because the failure is not a numerical one.

Between two vertices in different components the effective resistance is infinite. There is no path, no current flows, and the potential difference for a unit injection is unbounded. That is the correct answer and it is not a number, so a routine that returns one has computed something else.

What it has computed depends on how it failed. The grounded matrix of a disconnected graph is singular — the kernel has one dimension per component, and grounding one vertex removes only one of them — so the elimination hits a zero pivot. On the graphs in this field it hits a pivot of about 10⁻¹⁵ rather than exactly zero, for the reason the grounding essay measured: the elimination’s arithmetic is not exact even when the row sums are. So the solve proceeds, divides by a rounding error, and returns a resistance of order 10¹⁵ — a large number where the answer is infinity, from a computation that reported no error.

The routine here refuses instead, by counting components first. That check is a breadth-first search and costs less than one step of the elimination it precedes, and it converts a silently wrong number into a stated refusal. It is the same move the deliberate-zero essays argue for: a test the arithmetic cannot make reliably, made once, by a route that does not use the arithmetic.

At other settings

Resistance to 11 vertices, against an answer that is a ratio of integersEffective resistance from vertex 0 to every other vertex of the path 12, 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 0 for the elimination and 4.2·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 11 against 11.135791110⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1vertexrelative error against the exact answerthree routes, one numberworst, by elimination0worst, by spectrum4.2·10⁻¹⁵solve residual0Foster's sum11n − 111difference0the answer is a ratio of integersso the error is known
Fig. 3 The path, where the resistance is exactly the hop count and the rationals are integers.
Resistance to 11 vertices, against an answer that is a ratio of integersEffective resistance from vertex 0 to every other vertex of the complete 12, 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 6.66·10⁻¹⁶ for the elimination and 5·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 11 against 11.135791110⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1vertexrelative error against the exact answerthree routes, one numberworst, by elimination6.7·10⁻¹⁶worst, by spectrum5·10⁻¹⁶solve residual1.4·10⁻¹⁵Foster's sum11n − 111difference7.1·10⁻¹⁵the answer is a ratio of integersso the error is known
Fig. 4 The complete graph, where every resistance is 2/n.
Resistance to 19 vertices, against an answer that is a ratio of integersEffective resistance from vertex 0 to every other vertex of the grid 4×5, 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 7.79·10⁻¹⁶ for the elimination and 1.38·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 19 against 19.1471013161910⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1vertexrelative error against the exact answerthree routes, one numberworst, by elimination7.8·10⁻¹⁶worst, by spectrum1.4·10⁻¹⁵solve residual2.2·10⁻¹⁵Foster's sum19n − 119difference3.6·10⁻¹⁵the answer is a ratio of integersso the error is known
Fig. 5 A larger grid, where the exact route is still affordable and the errors have not grown.
Resistance to 15 vertices, against an answer that is a ratio of integersEffective resistance from vertex 0 to every other vertex of the hypercube 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 8.33·10⁻¹⁶ for the elimination and 9.52·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 elimination8.3·10⁻¹⁶worst, by spectrum9.5·10⁻¹⁶solve residual9.1·10⁻¹⁶Foster's sum15n − 115difference0the answer is a ratio of integersso the error is known
Fig. 6 A hypercube, whose resistances have a closed form in binomial coefficients.
Resistance to 15 vertices, against an answer that is a ratio of integersEffective resistance from vertex 0 to every other vertex of the star 16, 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.55·10⁻¹⁵ for the elimination and 8.88·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.6·10⁻¹⁵worst, by spectrum8.9·10⁻¹⁶solve residual2.1·10⁻¹⁵Foster's sum15n − 115difference1.8·10⁻¹⁵the answer is a ratio of integersso the error is known
Fig. 7 A star, where every non-central resistance is exactly two.
344 of 1225 edges keep every eigenvalue and no degreeA fifty-vertex complete graph sparsified by keeping 400 samples drawn in proportion to each edge's effective resistance and reweighted by the reciprocal of its probability, which leaves 344 distinct edges of 1225. The filled curve is the ratio of each eigenvalue of the sample's Laplacian to the original's, in ascending order: it stays between 0.432 and 1.67, so every quadratic form, every cut and every solve is preserved to that factor. The open curve is the ratio of each vertex's degree, which runs from 0.562 to 1.5 — half the graph's degrees are wrong by more than a third. And the graph's diameter goes from 1 to 3: no shortest path survives. A sparsifier preserves what the Laplacian says and nothing else about the graph, and the two are easy to confuse because they are the same object.19172533414911.251.51.752indexsample ÷ originalkept, and not keptedges kept344of1225eigenvalue ratio, low0.43high1.7degree ratio, low0.56high1.5diameter, after3filled dots are eigenvaluesopen dots are degrees
Fig. 8 What sampling by resistance preserves, which is the next essay in this anchor.
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. 9 The grid, whose resistances the hero figure measures.
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. 10 The free parameter in the grounded route, which the resistance itself does not depend on.
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. 11 The spectrum the spectral route sums over.
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. 12 The same eigenvalues weighted differently, as a bound on a cut.
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. 13 The site’s other exactly known answer, in the field that introduced the habit.
Past the cliff: what each method returnsLoss of orthogonality at four condition numbers past κ²u = 1. Cholesky QR returns a factor whose implied Q is 0.37 away from orthogonal at κ = 10⁸ and 1.49 at 10¹² — and at 3·10¹⁰ it refuses outright, on a pivot of -6.5·10⁻¹⁷. The sweep and the tree return a usable factorisation of every one of these matrices.‖QᵀQ − I‖ of the implied Qκ = 10⁸, Cholesky0.37κ = 10⁸, sweep8.5·10⁻⁹κ = 10¹⁰, Cholesky1.3κ = 10¹⁰, sweep3·10⁻⁷κ = 3·10¹⁰, Choleskyrefusedκ = 3·10¹⁰, sweep6.7·10⁻⁶κ = 10¹², Cholesky1.5κ = 10¹², sweep1.4·10⁻⁴the safe run is the one that failsrefusals in the range1wholly non-orthogonal returns2the pivot it refused on-6.5·10⁻¹⁷one of these outcomes is safeand it is the refusal
Fig. 14 A routine that returns a number where the answer is infinity, which a disconnected graph makes this one do unless it checks first.
Backward and forward error of two routes to x, on 30×30 systems across eight decades of κBoth routes start from the same LU factorisation. The LU solve's backward error is 2.2·10⁻¹⁷ at every conditioning — a flat line at the unit roundoff. Multiplying by the explicitly formed inverse gives 4.5·10⁻⁵ at κ = 10¹⁴, a slope of 0.94 against κ. The two forward errors, drawn above them, are 2.8·10⁻⁴ and 0.015 — within a factor of 54, which is why the difference between the two methods is invisible to anyone measuring how wrong the answer is.10²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1κ₂(A)relative errorforward, A⁻¹bforward, A\bbackward, A⁻¹bbackward, A\bat κ = 10¹⁴η, LU solve2.2·10⁻¹⁷η, via the inverse4.5·10⁻⁵forward, LU solve2.8·10⁻⁴forward, via the inverse0.015one factorisation, two ways to use itand one of them forfeits the backward error
Fig. 15 Forming an inverse against solving with it, in the elimination field.
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. 16 The two errors, of which this essay can measure both.
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. 17 The amplifier that would predict a larger error than the one measured.
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. 18 The identity the measured errors here are 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. 19 The precision knob, on a solve whose exact answer is known.
Conjugate gradients at κ = 104, against the bound κ permitsA semi-logarithmic plot of the relative A-norm error against iteration count. The measured curve falls below a smooth dashed curve showing the classical condition-number bound.0408012016020024010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration‖e‖_A / ‖e₀‖_Ameasuredκ bound119 steps40×40, spectrum spread evenly in logbound permits 1417
Fig. 20 The iteration a large resistance computation would use instead of an elimination.
What a rank-10 approximation can achieve, by spectrumA semi-logarithmic plot of singular value against index for three spectra — geometric decay, algebraic decay, and flat — with the rank-ten approximation error marked on each.1112131415110⁻³10⁻²10⁻¹1index jσⱼσ11geometric, 0.85ʲalgebraic, j^−1.00flatmeasured, and equal to σ₁₁rank-10 error, geometric0.2rank-10 error, algebraic0.091rank-10 error, flat160×60, spectrum chosen rather than the entriesthe matrix decides, not the method
Fig. 21 A spectrum whose small end dominates a sum like the spectral route’s.
Singular values of a rank-4 matrix with noise of relative size 10⁻⁸Ten singular values on a logarithmic axis. The first four sit near one; the rest sit at the noise level, and the vertical distance between the two groups is the evidence for the rank.1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision
Fig. 22 A threshold deciding an integer, which this quantity needs none of.
How close Hager's estimate is to the true κ₁, over 200 seeded 8×8 matricesFive bars. The estimate is exactly the true condition number on 81% of the sample and inside ten per cent on 87%; the worst underestimate in the whole sample returns 38% of the truth. The last bar is the matrix built to defeat it, at 7.7%, well below anything the random sample reached.each bar is a percentage — of the sample, or of the true condition numberexactly right80.5%inside 10%87.0%inside a factor of 287.0%worst in the sample, ×10037.7%the constructed matrix, ×1007.7%usually exactexact share0.81worst of the sample0.38the constructed matrix0.077a routine that is right most of the timeand never wrong in the safe direction
Fig. 23 An estimate rather than an exact answer, which most of this site has to settle for.
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. 24 A bound never attained, in the field that measured it first.
Two perturbation bounds and the error that was measured, on a 8×8 matrix spread over 8 decades of unitsThree curves against the size of an entrywise relative perturbation. The normwise bound κ_∞·ε is a valid bound and sits 4·10⁷ times above the componentwise one cond(A, x)·ε, which is also a bound and is nearly attained by the worst of forty random perturbations at each size.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1relative size of the entrywise perturbationrelative forward errorκ_∞ · εcond(A,x) · εmeasuredboth bounds holdκ_∞(A)1.9·10⁸cond(A, x)4.8ratio of the bounds4·10⁷both curves above the data are boundsand only one of them is a measurement
Fig. 25 An error measured entry by entry, which the exact route makes possible here.
One real vector, 23 candidate cuts, and the best of them is number 12The Fiedler vector of the barbell 12, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.14435. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 12 at a conductance of 0.007519 against a worst prefix of 1 — a factor of 133 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.0481216202410⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.00752, the best prefixthe rounding stepλ₂0.14cuts considered23best conductance0.0075at k =12worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs
Fig. 26 A bottleneck, which is what a large effective resistance is measuring.
κ 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. 27 Resistance summed over a tree’s paths, which is the quantity two essays along.

Where this goes next

the matrix, measuredvertices40edges223‖L·1‖∞0zero eigenvalues1components, by search1λ₂1.5laid out at its own eigenvectorsand the row sums are exactly zero A matrix with no numbers in it A graph arrives as vertices and edges. Two different matrices can be built from it, they answer different questions, and one of them has a null vector that is exact — the only object on this site whose kernel is known before anything runs. 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 An answer that is known Almost every demonstration of numerical error estimates the error by computing the same thing more carefully. The Hilbert matrix does not need that: its inverse is a closed form in integers, so the true answer is available exactly and the error is measured rather than approximated. 19172533414911.251.51.752indexsample ÷ originalkept, and not keptedges kept344of1225eigenvalue ratio, low0.43high1.7degree ratio, low0.56high1.5diameter, after3filled dots are eigenvaluesopen dots are degrees A graph with a tenth of the edges Keeping 344 of 1,225 edges, sampled by effective resistance and reweighted, preserves every eigenvalue of the Laplacian to within a factor of 1.7. It preserves no degree — half of them are wrong by more than a third — and it takes the diameter from one to three.

What links here

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

Reads more easily once this is understood

Essays that name this one as worth reading first.

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.

Connected componentsEffective resistanceExact ground truthFoster theoremGraph laplacianGroundingImportance samplingMatrix tree theoremMetricPseudoinverseSpectral decompositionSpectral sparsification