Skip to content
-14 -12 -10 -8 -6 -4 -2 0 10⁻¹⁷ 10⁻¹³ 10⁻⁹ 10⁻⁵ 10⁻¹ 10³ 10⁷ 10¹¹ 10¹⁵ log₁₀ μ — the barrier parameter condition number, and relative error κ₂, condensed κ₂, augmented error, condensed error, augmented against a BigInt answer κ₂ augmented, μ = 10⁻¹⁴ 3·10¹⁵ its relative error 10⁻¹⁵ κ₂ condensed 2.4·10¹⁶ its relative error 0.31 the same step, written two ways and only one of them is solvable
Interior-point conditioning
1
A condition number sent to infinity
2
The active set before the digits
3
Two repairs for one symptom
4
A test with no tolerance in it
4 essays · constraint
10⁻⁹ 10⁻⁶ 10⁻³ 1 10³ 10⁶ 13 21 29 37 κ · u significand bits κu = 1 a bound was proved the method refused it never returns a wrong bound largest κu with a proof 0.45 smallest κu without one 0.89 cases refused, of the grid 13 a refusal is not a wide bound — it is no bound at all and it is the only failure mode here
Interval
1
A bound that is proved
2
Proving the answer is in the box
3
Where the box is cut
4
Nine steps of pessimism
4 essays · arithmetic
λ = 10 5 times λ = 9.5 5 times λ = 9 5 times λ = 8.5 5 times λ = 2.95 2 times λ = 2.9 2 times eigenvalues that arrived more than once — the matrix has 40 distinct ones a spectrum with the wrong multiplicities extra copies, no reorthogonalisation 25 extra copies, full reorthogonalisation 0 worst relative error among the copies 1.9·10⁻⁸ steps taken of 80 asked for, full 40 no arithmetic error was made every one of these is right to eight digits
Lanczos
1
An eigenvalue that arrives twice
2
Restarting is a filter
3
Keeping the vectors, and losing the bound
4
The same budget, spent five ways
4 essays · spectra
0 2 4 6 8 10⁻¹⁷ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² 10¹ log₁₀ γ, the change of units relative error forward error η, the quadratic η, the linearisation against a closed form η(linearisation), worst 7.6·10⁻¹³ η(quadratic), worst 1.2·10⁻⁴ forward error, worst 0.0013 coefficient spread 4.2·10¹⁵ the solver is right at every stop about a problem nobody asked
Linearisation backward error
1
A backward-stable answer to a problem nobody asked
2
Six routes to one spectrum
3
A perturbation that moves every coefficient
4
The number that moves when the problem does
4 essays · polynomial
10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁻¹⁴ 10⁻¹ 10¹² 10²⁵ 10³⁸ 10⁵¹ 10⁶⁴ δ, the gap between consecutive eigenvalues relative error in eᴬ an answer with no correct digits V f(Λ) V⁻¹ scaling and squaring ‖A(δ) − A₀‖ exact eigenvalues throughout κ(V) at the smallest δ 3.3·10⁸² eigen route 2.9·10⁶⁵ scaling and squaring 4.1·10⁻¹² distance to the limit 7·10⁻¹² the eigenvalues are the diagonal and they are exact at every stop
Matrix function
1
A function of a matrix is not a function of its entries
2
The series that has to be squared back
3
The vector was what was wanted
4
The error the method already knows
4 essays · spectra
-2 -1 0 1 2 3 4 -5 -3 -1 1 3 5 real part imaginary part 4 inside a countable spectrum inside the contour 4 drawn 12 existing ∞ worst branch residual 1.6·10⁻¹⁵ there is no last eigenvalue so the question has to change
Nonlinear eigenvalue
1
A problem with infinitely many eigenvalues
2
A ceiling with a knob on it
3
The conditioning that rises with the ceiling
4
Where a contour's budget should go
4 essays · polynomial
10¹ 10⁴ 10⁷ 10¹⁰ 10¹³ 10¹⁶ 10⁻¹⁷ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² 10¹ κ(B) relative error, and asymmetry via B⁻¹A via Cholesky asymmetry of B⁻¹A u · κ(B) against a spectrum known exactly slope, via B⁻¹A 0.92 slope, via Cholesky 0.98 worst ratio between them 2.3 asymmetry of B⁻¹A 1.1 the symmetry claim is true and it is not about the accuracy
Pencil
1
Two matrices and one problem
2
An eigenvalue with no value
3
A problem with no answer
4
The largest gap is inside the null space
4 essays · spectra
-18 -15 -12 -9 -6 -3 0 0 log₁₀ ‖PKPᵀ − LDLᵀ‖ / ‖K‖ share of orderings best worst existence and stability factorise 1 unregularised 0.69 worst growth 6.4·10⁵ growth × γ 0.64 the ordering is free to choose and not free of consequence
Quasi-definite
1
The regularisation that legalises every order
2
The perturbation that does the work
3
A shift that certifies a saddle
4
The residual turns before the error doubles
4 essays · constraint
1 2 3 4 5 6 7 8 9 10 10⁻¹⁸ 10⁻¹⁵ 10⁻¹² 10⁻⁹ 10⁻⁶ 10⁻³ 1 index singular value cutoff, σ₁ · 10⁻¹⁰ numerical rank 10 gap 8.2·10⁶ an opinion true rank 4 10×10, built with 4 nonzero values rank is a decision
Rank
2
Rank is a decision
3
The cheap rank and what it cannot see
4
A rank that depends on the thread count
5
A good curve and a bad verdict
4 essays · spectra
10² 10³ 10⁴ 10⁻¹⁷ 10⁻¹⁶ 10⁻¹⁵ 10⁻¹⁴ 10⁻¹³ 10⁻¹² steps taken ‖RᵀR − AᵀA‖ ⁄ ‖AᵀA‖ the bound, linear in the steps √k · u every step safe, the chain not drift after the run 3.9·10⁻¹⁴ the bound there 3.3·10⁻¹³ √k · u there 6.1·10⁻¹⁵ worst single amplification 2.7 worst leverage met 0.69 refreshes 1 backward stable once and three thousand times is a different claim
Sequence stability
1
Stable once, and three thousand times
2
The repair the drift did not need
3
The answer the last window left
4
The step the two rows owe
4 essays · sequence
the smallest perturbation of any kind — 1.89·10⁻¹⁷ the smallest Toeplitz one — 2.65·10⁻¹³ both exact for the same x̂ smallest of any kind 1.9·10⁻¹⁷ smallest Toeplitz one 2.7·10⁻¹³ the price of the constraint 1.4·10⁴ diagonal defect, unconstrained 0.97 an exact answer to a nearby problem of a kind nobody posed
Structured backward error
1
A nearby problem of the wrong kind
2
The condition number of the model
3
A perturbation that keeps the symmetry
4
The number that cannot rank them
4 essays · structure
5 4 5 5 4 5 5 4 5 4 5 5 5 5 4 5 4 5 5 4 5 5 4 5 5 4 5 4 5 4 5 5 5 5 5 5 4 5 4 5 4 5 5 4 5 5 4 5 5 4 5 4 5 5 5 5 4 5 4 5 5 4 5 5 4 5 rows and columns, in the order the points arrive dark: kept dense · light: two thin factors, rank printed the strong partition blocks 112 kept dense 46 largest rank 5 numbers stored 2.7·10⁴ relative compression error 3.4·10⁻¹⁰ the picture is decided before a number is read
Admissibility
1
Which pairs are allowed to be small
2
The test that costs what it saves
3
The same matrix, numbered twice
3 essays · hierarchy
10¹ 10³ 10⁵ 10⁷ 10⁹ 10¹¹ 1 10¹ 10² 10³ 10⁴ condition number of the matrix growth factor bound 2^11 partial pivoting Cholesky no pivot to gain from Cholesky growth, every κ 1 Cholesky interchanges 0 partial pivoting, worst 9 the bound, 2^11 2048 both eliminations reach the same growth and only one of them had to swap to get there
Cholesky
1
A factorisation with nothing to pivot for
2
When symmetry is not enough
3
Where the multipliers go
3 essays · elimination
the estimator maximises this quantity over the columns it visits column 1 ‹visited› 12 column 2 ‹the answer› 114 column 3 11.4 column 4 11.4 column 5 11.4 column 6 11.4 column 7 11.4 column 8 11.4 column 9 11.4 column 10 11.4 column 11 11.4 column 12 11.4 estimate 12.0 a walk that stopped early the estimate returned 12 the true 1-norm 114 columns visited 1 products with the matrix 5 the walk's own stopping test fired and every column it could see was smaller
Condition-estimation
1
An estimate that can be fooled
2
The tail a sample never reaches
3
Two columns see what one walk cannot
3 essays · error
1 10¹ 10² 10³ 10⁴ 10⁵ 10⁶ 10⁷ 0 0.25 0.5 0.75 1 amplification of the input perturbation fraction of directions at or below κ = 10·10⁵ worst found 7.6·10⁵ 6×6, 200 directions median reaches 0.29 of κ
Conditioning
1
The condition number is an amplifier
2
A tensor that cannot be decomposed
3
The roots are not the coefficients
3 essays · error
0 15 30 45 60 75 90 105 120 10⁻² 10⁻¹ 1 10¹ step relative size least error: 20 discrepancy stop: 7 error residual the knob is an integer least error, at step 20 error there 0.14 error at step 120 6 the residual falls at every step the error turns and keeps rising
Deliberate zero
1
The zero you are allowed to write
2
Deciding that a zero has arrived
3
A tolerance is priced by the problem
3 essays · error
10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ 10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ size of the perturbation ‖δA‖ how far the eigenvalues move Jordan block, ε^(1/8) symmetric, ≤ ‖δA‖ rounding error alone moves it to 10⁻² six seeds per symmetric point; Jordan is closed form symmetry beats precision
Eigen conditioning
1
Symmetry is worth more than precision
2
A condition number for one eigenvalue
3
The gap decides the eigenvector
3 essays · spectra
3 4 5 6 7 8 9 10 11 12 1 10¹ 10² 10³ 10⁴ 10⁵ 10⁶ n widest intermediate, in bits rationals, not reduced fraction-free · rationals reduced · the answer one answer, three widths n 12 answer 40 Hadamard bound 52 fraction-free 40 reduced rationals 39 unreduced 1.4·10⁶ the error is zero on every curve the cost is the length of the numbers
Exact cost
1
An answer with no error in it
2
The answer is longer than the question
3
An exact answer to a measured problem
3 essays · exact
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
All essays