Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Pseudoinverse — where it appears

The inverse of a matrix restricted to the complement of its kernel. It appears in the definition of effective resistance and is never formed: what is wanted is a few quadratic forms in it, and those are one factorisation away.

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

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 laplacianGroundingConditioningConnected componentsDeflationEffective resistanceExact ground truthFoster theoremImportance samplingMatrix tree theoremMetricNormalised laplacian

All concepts