Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Effective resistance — where it appears

The potential difference between two vertices when one unit of current is injected at the first and drawn from the second. It is defined by a linear system with no combinatorial route to it, and the resistances of a graph's edges sum to exactly n - 1.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

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

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.

graph · effective resistance 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.

graph · effective resistance 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.

graph · graph elimination

Named alongside it

The objects these essays reach for when they reach for this one.

Graph laplacianFoster theoremImportance samplingSpectral sparsificationCombinatorial preconditioningConditioningConnected componentsDegree sequenceExact ground truthGeneralised eigenvalueGroundingMatrix tree theorem

All concepts