Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Foster theorem — where it appears

The identity that the weighted effective resistances of a connected graph's edges sum to exactly n - 1, whatever the graph is. It gives a computation a check against a number derived from the vertex count rather than from another routine.

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

Also named here as importance sampling, spectral sparsification — the same set of essays touches all of them, so they are one junction rather than several.

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

Named alongside it

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

Effective resistanceGraph laplacianImportance samplingSpectral sparsificationConnected componentsDegree sequenceExact ground truthGroundingMatrix tree theoremMetricPseudoinverseQuadratic form

All concepts