Skip to content
10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 1 10¹ 10² 10³ 10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ relative change in the coefficients, along the worst direction relative increase in the residual coefficients doubled 39% change, fit unmoved in the sixth digit 308×: the third digit moves κ(A) = 3.6·10⁶. Exact arithmetic would pick one point on this floor. It would not raise it. 24 points, degree 9, monomial basis the data leaves them free
Fitting
3
The valley with no bottom
4
A basis built from the points
5
The degree that is safe to overshoot
3 essays · leastsquares
[½, 1) [1, 2) [2, 4) 0.5 1 2 4 gap 0.125 gap 0.25 — twice as wide 8 values per octave spacing doubles at each power of two
Floating-point
1
What a float can hold
2
The other half of a format
3
Eight bits, and a format that breaks the rules
3 essays · arithmetic
20 22 24 26 28 30 32 10⁻¹⁷ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² k, where the entries are near 2ᵏ relative error of the determinant as written fused: exact products need 54 bits one rounding, the whole answer true determinant 1 naive, k = 30 0 fused, k = 30 1 first wrong at k 27 sizes returning 0 6 both forms conform and the source does not say which
Fma contraction
1
One multiply the compiler removed
2
A matrix that is definite on one machine
3
A square that evaluates negative
3 essays · machine
1 2 3 4 5 6 7 8 9 10 10⁻¹⁹ 10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ k λₖ₊₁ ÷ λ₁, and the bound Zₖ² the Gramian predicted from two numbers states 30 κ of the spectrum 389 λ11 ÷ λ₁ 2.5·10⁻⁸ the bound there 5.2·10⁻⁴ the cliff everything rests on and the reason for it
Gramian decay
1
Why a Gramian can be truncated at all
2
Where to put the poles of a rational function
3
Bracketing an error nobody can measure
3 essays · reduction
0 5 10 15 20 25 30 35 0 59 118 177 236 295 vertices eliminated edges of fill so far minDegree: 71 natural: 125 reverse: 125 random: 160 maxDegree: 293 fill, by ordering minDegree 71 natural 125 reverse 125 random 160 maxDegree 293 edges to start 60 eliminating a vertex makes a clique and the order decides how big
Graph elimination
1
Eliminating a vertex is a graph operation
2
A preconditioner that is a tree
3
A count that comes out of a determinant
3 essays · graph
a triangle and a square, joined K₂,₃ with a pendant edge 1 2 3 4 5 6 0 1 2 3 4 5 6 index eigenvalue the same, and not the same vertices each 6 edges each 7 spanning trees 12 spectra differ by 5.3·10⁻¹⁵ highest degree, left 4 highest degree, right 3 one has a triangle the other is bipartite
Graph invariant
1
The spectrum is not the graph
2
A finer invariant that hears less
3
Each spectrum hears the other's pairs
3 essays · graph
the matrix, measured vertices 40 edges 223 ‖L·1‖∞ 0 zero eigenvalues 1 components, by search 1 λ₂ 1.5 laid out at its own eigenvectors and the row sums are exactly zero
Graph laplacian
1
A matrix with no numbers in it
2
Two Laplacians of one graph
3
The vertex nobody solves for
3 essays · graph
5 6 7 8 9 10 10⁴ 10⁵ 10⁶ 10⁷ 10⁸ 10⁹ log₂ n multiplications dense factorisation, n³⁄3 the recursion, counted where the format starts paying ratio at n = 64 1.5 ratio at n = 512 0.16 exponent, first doubling 2.1 exponent, last doubling 1.7 backward error 1.4·10⁻¹⁰ cheaper is a size not a property
Hierarchical solve
1
Where the format starts paying
2
The accuracy worth paying for
3
The knob that moved two things
3 essays · cost
the invariant plane solid: before dashed: after same perturbation, two questions the vectors turned, radians 0.029 the plane turned, radians 7.6·10⁻⁸ what left the plane 5.6·10⁻⁸ drawn in the unperturbed plane's own basis a radius is not determined; the circle is
Invariant subspace
1
The plane survives what its vectors do not
2
An eigenvalue one vector cannot see
3
How wide the block should be
3 essays · spectra
0 36 72 108 144 180 216 0 2 4 6 8 10 12 eigenvalues in order λ the closed form marks: the assembled matrix, decomposed a spectrum nobody computed rows of the matrix 216 numbers that describe it 108 λ smallest 0.59 λ largest 11 worst |computed − exact| 7.1·10⁻¹³ the matrix is never needed and neither is its decomposition
Kronecker
1
An index that is a pair
2
A solve that is d decompositions
3
Five indices are cheaper than two
3 essays · tensor
0 1 2 3 4 5 6 10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ refinement step ‖x − x*‖ / ‖x*‖ a full double-precision solve residual in 24-bit residual in double one argument apart κ·u of the factorisation 6·10⁻⁴ double residual, final 3.2·10⁻¹³ same-precision, final 1.3·10⁻⁴ 30×30, κ = 10⁴, same factors in both runs identical cost
Mixed-precision
1
Buying the accuracy back
2
Where the hardware went
3
The part of a solver that may be rounded
3 essays · arithmetic
3 4 5 6 7 8 9 10 11 1 10¹ 10² n bits the budget and what it buys random, bound 47 random, actual 33 primes needed 2 Hadamard n = 8, bound 13 Hadamard n = 8, actual 13 the count is decided by a theorem before any arithmetic happens
Modular lift
1
How many primes the answer needs
2
A prime that divides the answer
3
A fraction recovered from one remainder
3 essays · exact
10⁻¹ 1 10¹ 10² 10³ 10⁻¹⁷ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ s, on the real axis |H − Hᵣ| ÷ |H| exact where asked points 4 conditions bought 8 worst at a point 5.3·10⁻¹⁶ worst away from one 8.4·10⁻⁴ 4 points, 8 conditions and no bound in between
Moment matching
1
Exact at the points that were named
2
A basis that is the same subspace and not the same thing
3
Interpolating at the model’s own poles
3 essays · reduction
0 2 4 6 8 10 10⁻¹¹ 10⁻⁹ 10⁻⁷ 10⁻⁵ 10⁻³ 10⁻¹ rank kept in every mode relative error dashes above: √(Σ tail²), the upper bound dashes below: max tail, a floor under the best solid: what the projection returns smooth: pinned to the upper bound rank 10 error 1.1·10⁻¹¹ its upper bound 1.1·10⁻¹¹ the lower bound 6.3·10⁻¹² error ⁄ bound 1 error ⁄ lower 1.7 inside the bound and sitting on it
Multilinear rank
1
A decomposition made only of SVDs
2
The orthogonality that cannot be diagonal
3
A compression of 10¹⁴ that still does not fit
3 essays · tensor
κ(A) = 10⁶ throughout · κ(H) = 100 · the answer is the same answer for every basis orthonormal — κ(Z) 1 κ(ZᵀHZ) 25.6 relative error 1.07·10⁻¹⁵ first m basic — κ(Z) 1.99·10⁸ κ(ZᵀHZ) 3.8·10¹⁶ relative error 0.0518 pivoted basic — κ(Z) 2.06 κ(ZᵀHZ) 31.9 relative error 6.71·10⁻¹⁶ what the choice costs density, orthonormal 1 density, fundamental 0.5 κ(ZᵀHZ) ÷ κ(Z)², naive 0.96 error, pivoted choice 6.7·10⁻¹⁶ every one of them is a basis and one of them loses fourteen digits
Null-space basis
1
The basis nobody chose on purpose
2
The tree the resistances choose
3
Spread resistances make the loops easy
3 essays · orthogonality
[ ε 1 ; 1 1 ] x = [ 1 ; 2 ], exact answer (1.000000, 1.000000) with partial pivoting 1 1 0 1 U after elimination 1.000000 1.000000 computed x backward error 0 forward error 0 without 10⁻¹⁷ 1 0 -1·10¹⁷ U after elimination 0.000000 1.000000 computed x backward error 0.25 forward error 0.71 no error is raised growth 10¹⁷
Pivoting
2
The swap that is not optional
3
The pivot that reads the units
4
A pivot that searches one row and one column
3 essays · elimination
0 2 4 6 8 10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ log₁₀ γ, the change of units forward error as written after scaling one change of variable unscaled, worst 0.0013 scaled, worst 1.7·10⁻¹³ orders recovered 10 scaled coefficient spread 4.5 the answer was never the problem the units were
Polynomial scaling
1
The scaling that buys ten orders
2
An estimate that does not move
3
Two groups need two reductions
3 essays · polynomial
0 5 10 15 20 25 30 35 40 10⁻¹¹ 10⁻⁹ 10⁻⁷ 10⁻⁵ 10⁻³ 10⁻¹ iteration ‖r‖ / ‖b‖ plain CG IC(0) CG what the preconditioner did κ(A) 48 κ(L⁻¹AL⁻ᵀ) 5.1 ‖A − LLᵀ‖/‖A‖ 0.083 2D Laplacian, n = 100 √κ ratio predicts 3.07×
Preconditioning
1
Changing the condition number on purpose
2
A preconditioner that changes sign
3
A speedup with a ceiling of its own
3 essays · iterative
0 14 28 42 56 70 84 98 10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² iteration change between iterates two rates, one curve α 0.85 λ₂(P) 0.9 predicted rate 0.77 measured 0.77 iterations 108 against the solve 10⁻¹⁶ the upper dashed line is αᵏ the curve is on the other one
Random walk
1
A ranking that is an eigenvector
2
The rate is the second eigenvalue
3
A chain with no stationary vector
3 essays · graph
0 8 16 24 32 1 1.1 1.2 1.3 1.4 terms added, each followed by a truncation error ⁄ best rank-k error optimal terms with nothing in common a subspace that drifts the rounding nobody should have feared drifting, worst excess 1 independent, worst excess 1 a linear bound would say 32 energy discarded, first 1.8·10⁻⁷ energy discarded, last 0.03 thirty-two roundings and four per cent
Recompression
1
The rounding that was not the problem
2
The count that is not the budget
3
A knob calibrated in residuals
3 essays · hierarchy
All essays