Numerical Linear Algebra
where the algebra stops being the arithmetic
Ladder

Graph elimination — the ladder

3 distinct arguments against one idea, from the one that introduces it to the one that assumes the rest.
  1. 05101520253035059118177236295vertices eliminatededges of fill so farminDegree: 71natural: 125reverse: 125random: 160maxDegree: 293fill, by orderingminDegree71natural125reverse125random160maxDegree293edges to start60eliminating a vertex makes a cliqueand the order decides how big

    Eliminating a vertex is a graph operation

    Gaussian elimination on a Laplacian deletes a vertex and joins its neighbours into a clique with conductances wᵢwⱼ over Σw. The matrix that remains is still a graph — symmetric, zero row sums, nonpositive off the diagonal — and the ordering decides whether the fill is thirty-one edges or four hundred and sixty-five.

    rung 1 · graph
  2. 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.

    rung 2 · graph
  3. 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.

    rung 3 · graph

All ladders