Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Floating point — where it appears

The representation of real numbers as a sign, an exponent and a fixed number of significand bits. Its spacing doubles at every power of two, so it holds every integer up to 2^53 exactly and not one consecutive pair above it.

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

[½, 1)[1, 2)[2, 4)0.5124gap 0.125gap 0.25 — twice as wide8 values per octavespacing doubles at each power of two

What a float can hold

The representable numbers are not a fine fuzz spread evenly over the line. They are evenly spaced inside each power-of-two interval and twice as far apart in the next one up, and almost everything else in this subject is a consequence of that one fact.

arithmetic · floating point 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

Named alongside it

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

Backward errorCospectral graphsDeterminantError accumulationExact ground truthGraph eliminationGraph invariantGraph laplacianInteger overflowMachine epsilonMatrix tree theoremSignificand

All concepts