Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Grounding — where it appears

Removing a Laplacian's kernel by deleting one vertex's row and column, so that what is left is positive definite. Which vertex is a free parameter no account of the method mentions, and it moves the condition number by up to three orders.

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

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

1611162126110¹10²10³degree of the grounded vertexcondition number of what is left1, the best choicea parameter nobody setsvertices tried30best κ1at degree29worst κ898at degree1spread898one row and column deletedand it matters which

The vertex nobody solves for

A Laplacian is singular, so every solve with one has to remove its kernel first. There are three ways, they agree to fourteen digits, and the one everybody uses carries a free parameter that no account of the method mentions and that moves the condition number by nine hundred.

graph · graph laplacian 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

Named alongside it

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

Graph laplacianPseudoinverseConditioningConnected componentsDeflationEffective resistanceExact ground truthFoster theoremImportance samplingMatrix tree theoremMetricNormalised laplacian

All concepts