Skip to content
1 3 5 7 9 11 13 15 10⁻¹⁸ 10⁻¹⁵ 10⁻¹² 10⁻⁹ 10⁻⁶ 10⁻³ 1 vertex relative error against the exact answer three routes, one number worst, by elimination 4.8·10⁻¹⁶ worst, by spectrum 10·10⁻¹⁶ solve residual 1.5·10⁻¹⁵ Foster's sum 15 n − 1 15 difference 3.6·10⁻¹⁵ the answer is a ratio of integers so the error is known
Effective resistance
1
A distance computed by a solve
2
A graph with a tenth of the edges
2 essays · graph
H13 x = b, b formed exactly so that x = (1, 2, …, 13) 1 2 3 4 5 6 7 8 9 10 11 12 13 exact 1.0000 2.0000 3.0013 3.9786 5.1886 4.9930 10.4672 0.0489 21.2657 -2.5753 19.2147 8.9060 13.5113 computed 6.6 correct digits 4.8 correct digits 3.4 correct digits 2.3 correct digits 1.4 correct digit 0.8 correct digit no correct digits no correct digits no correct digits no correct digits no correct digits 0.6 correct digit 1.4 correct digit backward error 2.2·10⁻¹⁷ κ = 1.7·10¹⁸ The algorithm solved a neighbouring problem perfectly. That problem's answer is this one. right-hand side built in BigInt rationals the truth is known
Exact ground truth
2
An answer that is known
3
Balanced is not symmetric
2 essays · error
ℚ 6 𝔽2 4 𝔽3 5 𝔽5 6 𝔽7 6 𝔽11 6 𝔽13 6 𝔽101 6 𝔽65537 6 rank, by the ring the entries are read in the rank of one matrix over ℚ 6 over 𝔽2 4 over 𝔽3 5 over 𝔽5 6 over 𝔽7 6 nothing is rounded here and the answer still is not a property of the matrix
Exact rank
1
The rank depends on the ring
2
The field decides it, usually
2 essays · exact
0 2 4 6 8 10 12 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 1 iteration ‖r‖ / ‖b‖ Laplacian cyclic shift no progress at all every eigenvalue of the shift is on the unit circle and it predicts nothing
GMRES
1
The spectrum that predicts nothing
2
The basis decides what a filter is
2 essays · iterative
10² 10⁴ 10⁶ 10⁸ 10¹⁰ 10¹² 10¹⁴ 10⁻¹⁸ 10⁻¹⁵ 10⁻¹² 10⁻⁹ 10⁻⁶ 10⁻³ 1 κ₂(A) relative error forward, A⁻¹b forward, A\b backward, A⁻¹b backward, A\b at κ = 10¹⁴ η, LU solve 2.2·10⁻¹⁷ η, via the inverse 4.5·10⁻⁵ forward, LU solve 2.8·10⁻⁴ forward, via the inverse 0.015 one factorisation, two ways to use it and one of them forfeits the backward error
Inversion
1
The inverse that is never formed
2
The gap refinement can close
2 essays · elimination
0 8 16 24 32 40 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² conjugate gradient step relative residual above, on their own scale: rank asked 5, rank kept 3 solid: the budgeted residual · light: no budget budget 3 rank asked for 5 rank kept 3 residual, budgeted 3.8·10⁻⁴ residual, unbudgeted 1.6·10⁻¹⁴ numbers stored 150 the step asks for more at every step
Low-rank iteration
1
An iterate that must be made smaller
2
A run that is over at step five
2 essays · iterative
10¹ 10³ 10⁵ 10⁷ 10⁹ 10¹¹ 10¹³ 10¹⁵ 10⁻¹⁸ 10⁻¹⁵ 10⁻¹² 10⁻⁹ 10⁻⁶ 10⁻³ 1 κ₂(A), the matrix that was updated relative forward error Sherman–Morrison direct solve of A + uvᵀ one answer, two routes κ of the answer's matrix 1 κ of the matrix replaced 10·10¹³ update formula's error 2.5·10⁻⁴ direct solve's error 1.1·10⁻¹⁶ the question's condition number is 1 at every point on this axis
Low-rank update
1
A correction cheaper than the problem
2
The observation that cannot be removed
2 essays · leastsquares
darker is smaller: 10⁻¹⁰, 10⁻⁶, 10⁻³, 10⁻¹ one spectrum, two matrices spectral radius 0.8 reach of the 10⁻³ level 1.3 eigenvalues, all at 0.8 the circle is |z| = 1 and every eigenvalue is well inside it
Non-normality
1
The eigenvalues that are not there
2
A spectral radius that grows first
2 essays · spectra
s1 0 bits s2 0 bits s3 0 bits s4 0 bits s5 14 bits invariant factors, in bits two routes, and a conserved quantity det A -2.3·10⁴ Π invariants 2.3·10⁴ SNF widest 15 HNF widest 24 det of the transform -1 an algorithm and a definition agreeing as integers
Normal forms
1
What a determinant does not determine
2
Every entry under the determinant
2 essays · exact
A = H8 · κ = 1.5·10¹⁰ · both factorisations reconstruct A to 6·10⁻¹⁷ the diagonal is 1 in both — every column is a unit vector either way 1.000 0 0 0 0 0 0 0 0 1.000 0 0 0 0 0 0 0 0 1.000 0 0 0 0 0 0 0 0 1.000 0 0 0 0 0 0 0 0 1.000 0 0.002 -0.002 0 0 0 0 0 1.000 0.125 -0.133 0 0 0 0 0.002 0.125 1.000 -1.000 0 0 0 0 -0.002 -0.133 -1.000 1.000 classical Gram–Schmidt 1.000 0 0 0 0 0 0 0 0 1.000 0 0 0 0 0 0 0 0 1.000 0 0 0 0 0 0 0 0 1.000 0 0 0 0 0 0 0 0 1.000 0 0 0 0 0 0 0 0 1.000 0 0 0 0 0 0 0 0 1.000 0 0 0 0 0 0 0 0 1.000 Householder classical ‖QᵀQ − I‖ 1.4 Householder ‖QᵀQ − I‖ 1.4·10⁻¹⁵ largest off-diagonal 1 against 3.1·10⁻¹⁶ length is not angle
Orthogonality
1
Orthogonal is a number
2
An inner product with no fixed sign
2 essays · orthogonality
-47 -37 -27 -17 -7 3 13 23 33 0 1 2 3 4 log₁₀ of the vector's norm fp16 11 bits bfloat16 8 bits tf32 11 bits binary32 24 bits pale: the format's range · blue: √(Σ(xᵢ/m)²)·m · red: √(Σxᵢ²) fp16 and tf32 have the same eleven significand bits and their bars do not overlap
Overflow
1
A norm that overflows before it is a norm
2
The units that overflow before the answer does
2 essays · arithmetic
0 0.0939569 -2 -1.24498 -0.489961 0.265058 1.02008 1.7751 real part imaginary part two routes, one spectrum eigenvalues 16 rows 8 complex 16 against the closed form 2.1·10⁻¹⁵ n rows and 2n eigenvalues so the eigenvectors are not a basis
Polynomial eigenvalue
1
A matrix that depends on its own eigenvalue
2
One mass removed, and one eigenvalue gone
2 essays · polynomial
0 35 70 105 140 175 210 245 280 10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ iteration |subdiagonal entry| no shift Rayleigh Wilkinson two routes to one rate rate, from the spectrum 0.9 rate, measured 0.9 iterations, none / Wilkinson 45 symmetric 4×4, spectrum 8, 4, 2, 1.8 the dashed line is the prediction
The QR algorithm
1
The algorithm the libraries actually run
2
The form that makes it affordable
2 essays · spectra
-15 -13 -11 -9 10⁻¹³ 10⁻¹¹ 10⁻⁹ 10⁻⁷ log₁₀ of the defect, relative to the entry it sits in how far the answer moved the machine, on its own a tolerance with two sides machine band 3.2·10⁻¹² smallest caught 10⁻¹² its nearest run 4.6·10⁻¹² defects hidden 3 window, factor 1.4 below the band nothing is visible and above it everything is
Regression tolerance
1
What a regression test can ask for
2
Two machines, one certificate
2 essays · machine
10² 10³ 10⁴ 10⁻⁸ 10⁻⁷ 10⁻⁶ 10⁻⁵ 10⁻⁴ terms summed relative error +∞, −∞ 1.01 zero 1.00 stochastic 0.50 nearest 0.47 √n against n, fitted nearest, fitted exponent 0.47 stochastic, fitted exponent 0.5 toward +∞, fitted exponent 1 twelve seeds averaged at each size the slope is the bias, not the precision
Rounding
1
The direction the error leans
2
A coin flip that fixes the average
2 essays · arithmetic
1 2 3 4 5 6 7 10¹ 10² 10³ 10⁴ 10⁵ number of indices numbers entries: 6^d stored: 4n(d − 1) exponential against linear entries at d = 6 4.7·10⁴ numbers stored 120 ratio 389 slope against d 24 ‖T − Tₜₜ‖ ⁄ ‖T‖ 1.4·10⁻¹⁵ one line is n^d the other is a constant per index
Tensor train
1
The format that does not notice the dimension
2
The digit that costs more than the tensor
2 essays · tensor
10⁻¹ 1 10¹ 10² 10³ 10⁻¹¹ 10⁻¹⁰ 10⁻⁹ 10⁻⁸ 10⁻⁷ 10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ frequency ω |H(iω)| one function, two routes states 24 relative, ω ≤ 100 10⁻¹⁴ against the terms 3.9·10⁻¹⁵ ‖H‖∞ 0.09 24 states one function of one variable
Transfer function
1
A model that is a rational function
2
The definition asks for more of what defeats it
2 essays · reduction
6 × 6 × 6, rank 3 · 9 ≥ 8 1.0000 2 × 2 × 2, rank 3 · 6 < 8 0.0207 6 × 6 matrix, rank 3 · no condition 0.1089 worst agreement between two runs about the factors, 0 to 1 every run fits to 3·10⁻¹³ every run fits to 1.2·10⁻¹¹ every run factorises to 2.4·10⁻¹⁵ and none agrees with another the only thing that improves tensor, Kruskal holds 1 tensor, Kruskal fails 0.021 matrix 0.11 worst residual 1.2·10⁻¹¹ three successful fits one recoverable answer
Uniqueness
1
A factorisation that is unique for once
2
Unique, and not determined
2 essays · tensor
1 2 3 4 5 6 7 8 9 10 11 12 10⁻¹⁵ 10⁻¹³ 10⁻¹¹ 10⁻⁹ 10⁻⁷ 10⁻⁵ 10⁻³ 10⁻¹ degree of the approximant worst relative error on the target set chosen by the residual degree reached 12 error there 10⁻¹² even support, same degree 1.1·10⁻⁷ advantage 702 nearest support point 0.096 clustering ratio 1.5 filled: points chosen by the error open: points spread evenly
Adaptive interpolation
1
The points the algorithm chose
1 essay · polynomial
26 38 50 62 74 10⁻⁵ 10⁻³ 10⁻¹ rows in the linearisation ‖g − r‖ on the target set polynomial rational equal cost, two bases reach 0.06 largest size drawn 78 rational there 2·10⁻⁵ polynomial there 0.0015 the ratio 73 no winner on an easy target and two orders on a hard one
Approximant choice
1
Two approximants and one matrix size
1 essay · polynomial
All essays