Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Spanning tree — where it appears

A connected subgraph containing every vertex and no cycle, with n - 1 edges. Its Laplacian factorises with no fill, the number of them a graph has is a determinant, and the probability an edge is in a random one is its effective resistance.

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

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 57911131517192110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹vertices of the complete graphrelative sizethe algorithm is not the problemsizes counted18worst relative error9.4·10⁻¹⁵first wrong at n =16digits in the answer17spacing of doubles there8largest integer a double holds9·10¹⁵the elimination stays at the rounding levelthe format runs out

A count that comes out of a determinant

The number of spanning trees of a graph is the determinant of its grounded Laplacian, so it is a whole number known in advance. The elimination that computes it is backward stable at every size — and from sixteen vertices the answer is wrong, because the count has seventeen digits and a binary64 has sixteen.

graph · graph elimination a triangle and a square, joinedK₂,₃ with a pendant edge1234560123456indexeigenvaluethe same, and not the samevertices each6edges each7spanning trees12spectra differ by5.3·10⁻¹⁵highest degree, left4highest degree, right3one has a trianglethe other is bipartite

The spectrum is not the graph

Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits. One contains a triangle; the other is bipartite. Every method in this field that reads only the spectrum is answering about the class.

graph · graph invariant

Named alongside it

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

Graph laplacianCospectral graphsExact ground truthGraph invariantBackward errorBipartiteCharacteristic polynomialCombinatorial preconditioningConditioningDeterminantEffective resistanceFloating point

All concepts