Skip to content
0 0.25 0.5 0.75 1 -1 -0.5 0 0.5 1 mode frequency θ / π damping factor per sweep predicted measured ±0.333 a coarse grid sees two routes to one factor smoothing factor, scanned 0.33 smoothing factor, closed form 0.33 worst mode disagreement 4.4·10⁻¹⁶ 63 interior points, one sweep the left-hand end is what the coarse grid is for
Multigrid
1
The error smoothing cannot reach
2
The same problem on a coarser grid
3
A rate that does not notice the size
4
The coarse problem is a different problem
5
A smoother that stops being one
5 essays · iterative
natural 1739 reverse Cuthill–McKee 1354 minimum degree 1026 nested dissection 1413 matrix: 408 entries · dense factor: 10440 bandwidth 12 · 4.26× the matrix bandwidth 12 · 3.32× the matrix bandwidth 123 · 2.51× the matrix bandwidth 108 · 3.46× the matrix n = 144, five-point stencil every ordering fills in; none avoids it
Ordering
1
The order decides the memory
2
The least fill there is
3
An ordering that buys processors, not time
4
Two minima that are one minimum
5
The depth that is worse than both ends
5 essays · sparsity
0 4 8 12 16 20 10⁻¹ 10⁻⁰.⁵ 1 target rank k ‖A − Aₖ‖₂ published bound randomised σₖ₊₁, optimal how far apart the three are worst seed spread 1.6 bound / median at k = 12 5.9 median / optimum at k = 12 1.9 60×60, 6 seeds, oversampling p = 5 band is best to worst
Randomised
1
A bound that holds with probability
2
Randomisation does not create structure
3
An answer that changes with the seed
4
The rank a certificate charges
5
A sketch that finds the columns it can see
5 essays · randomised
0 2 4 6 8 10 12 14 16 18 20 22 10⁶ 10⁷ 10⁸ members served by one factorisation multiplications for the whole sequence does not converge the contraction rule drift 0.01 a member every member 1.6·10⁷ every 5 members 9.3·10⁶ contraction rule 9.2·10⁶ its factorisations 4 cliff at a period of 20 a factorisation has a shelf life and the cliff is past the optimum
Reuse
1
A factorisation kept past its date
2
Where the drift lands
3
What a rebuild is worth
4
What survives one step of the barrier
5
The penalty for keeping it is a ratio
5 essays · sequence
nothing 8.3% the right-hand side 16.5% the matrix, slowly 85.9% everything 100.0% what can be reused: the answer what can be reused: the factorisation what can be reused: the factorisation, for a while what can be reused: nothing share of the cost of a sequence that shares nothing what 12 members cost in factorisations same: factorisations 1 rhs: factorisations 1 drift: factorisations 4 independent: factorisations 12 what changes between the members decides what may be carried
Sequence of solves
1
The problem that arrives again
2
The order a batch arrives in
3
A warm start is degree zero
4
A straight path has nothing for a parabola to fit
5
The degree the history chooses
5 essays · sequence
the grid the operator came from an edge is a coupling the matrix calls strong kept interpolated what the entries decided coupling ratio, x against y 0.001 strong couplings across x 0 strong couplings along y 110 rows kept or dropped whole 11 11×11 grid, θ = 0.25 the coarse grid, from the matrix alone
Algebraic multigrid
1
The coarse grid the matrix chooses
2
A hierarchy with no grid behind it
3
The formula that was already optimal
4
The switch does not know which side is better
4 essays · iterative
0 0.367008 0.734017 1.10103 1.46803 1.83504 0 eigenvalue of P⁻¹K written down, then computed distinct 3 at 1 6 φ computed 1.6 off the closed form 2.9·10⁻¹⁴ 1 − φ 1 φ the preconditioner's effect is a theorem and the golden ratio is in it
Block preconditioning
1
Three eigenvalues, and two are the golden ratio
2
A preconditioner that need not know the constraint
3
One eigenvalue and two steps
4
Where the augmentation puts the cost
4 essays · constraint
0 2 4 6 8 10 12 14 16 18 0 2 4 6 8 10 12 14 16 18 distinct eigenvalues in the spectrum step the recurrence stops at the step is m, not n n = 30 throughout spectra drawn 8 every one breaking at m 8 worst residual at the breakdown 5.6·10⁻¹⁶ smallest gain over the step before 3.5·10¹⁰ an invariant subspace contains the answer and its dimension is what the method costs
Breakdown
1
The zero that means it is finished
2
The same zero, and nothing was found
3
The division that cannot be done
4
A proof that does not ask how large the matrix is
4 essays · iterative
classical Gram–Schmidt 4.62·10⁻¹⁰ modified Gram–Schmidt 1.49·10⁻¹² Householder, one sweep 2.03·10⁻¹⁴ reduction tree, 16 leaves 1.48·10⁻¹⁵ departure from orthogonality, logarithmic the tree, at four depths ‖AᵀA − RᵀR‖/‖AᵀA‖, depth 1 3.4·10⁻¹⁵ ‖AᵀA − RᵀR‖/‖AᵀA‖, depth 2 4.3·10⁻¹⁵ ‖AᵀA − RᵀR‖/‖AᵀA‖, depth 3 1.7·10⁻¹⁵ ‖AᵀA − RᵀR‖/‖AᵀA‖, depth 4 1.5·10⁻¹⁵ the same algebra, four times two of them are products of reflections
Communication
1
A reduction that changes the order
2
The message and the word
3
Doing it twice
4
Memory bought with messages
4 essays · cost
0 2 4 6 8 10 12 14 10⁻¹⁷ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² 10¹ 10⁴ 10⁷ 10¹⁰ log₁₀ τ — the weight on the constraint relative error against the exact answer τ = 1/√u Gram–Schmidt normal equations Householder QR the ceiling is the method's Householder, τ = 10¹⁴ 4.8·10⁻¹⁵ normal equations 14 Gram–Schmidt 4.9·10¹⁰ 1/√u 6.7·10⁷ a constraint is a weight at infinity and the solver decides how far infinity is
Constrained least-squares
1
A constraint is a weight at infinity
2
The reference was a method
3
The condition number that does not know
4
Feasible and wrong
4 essays · leastsquares
the matrix, lower triangle 408 entries its Cholesky factor 1739 entries · 1331 created → ‖A − LLᵀ‖/‖A‖ 1.4·10⁻¹⁶ fill, symbolic 1331 fill, numeric 1331 n = 144 · density 3.2% · bandwidth 12 same matrix, renumbered the answer is identical to rounding
Fill
1
The factor is not sparse
2
Two ends of the same arrow
3
The fill that is not independent
4
The cliff behind the count
4 essays · sparsity
for each previous column i, subtract the projection of column j onto qᵢ classical r[i][j] = qᵢ · a[j] ↑ the ORIGINAL column v = v − r[i][j] · qᵢ the three worst |qᵢ · qⱼ|: columns 7 and 8: 1 columns 6 and 8: 0.13 columns 6 and 7: 0.13 modified r[i][j] = qᵢ · v ↑ what is LEFT of it v = v − r[i][j] · qᵢ the three worst |qᵢ · qⱼ|: columns 1 and 8: 4.4·10⁻⁷ columns 2 and 8: 2.7·10⁻⁷ columns 3 and 8: 2.4·10⁻⁸ The two R factors agree to 1.2·10⁻⁶ relative. The two Q factors do not. the 8×8 Hilbert matrix one word, eight orders
Gram–Schmidt
2
Two Gram–Schmidts
3
The right-hand side as one more column
4
A stable block is not a stable basis
5
What the appended block inherits
4 essays · orthogonality
10⁻¹⁵ 10⁻¹² 10⁻⁹ 10⁻⁶ 10⁻³ 1 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 1 inner tolerance η, relative residual of the linear solve distance from the root after the step d² = 0.00138 distance before the step, 0.0372 109 354 723 1126 the number by each point is the iterations it cost eleven decades, one landing place distance before the step 0.037 its square 0.0014 where η = 10⁻³ lands 0.0025 where η = 10⁻¹⁴ lands 0.0025 iterations for the first 354 iterations for the second 1126 the accuracy that is thrown away measured against a root that is known
Inexact newton
1
The accuracy that is thrown away
2
A tolerance that reads its own residual
3
A guess worth two per cent
4
One line that buys a quarter of the run
4 essays · sequence
-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
0 5 10 15 20 25 30 35 40 10⁻¹⁷ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² 10¹ singular value, in order σ ⁄ σ₁ eight digits an independent draw per entry 1 ⁄ r a cliff, and a control 1/r rank at 10⁻⁸ 5 log r rank at 10⁻⁸ 5 noise rank at 10⁻⁸ 96 σ₂ ⁄ σ₁ 0.024 σ₆ ⁄ σ₁ 2.8·10⁻⁹ the block has full rank and five useful columns
Off-diagonal rank
1
A block nobody can call sparse
2
A rank that is a number of digits
3
The size the rank does not notice
4
The kernel with nothing to compress
4 essays · hierarchy
All essays