Skip to content
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
Iterative regularisation
1
A parameter that counts steps
2
The step that stops mattering
3
An expiry date the noise does not move
4
A step that is not a unit of work
5
The method that cannot use a smooth answer
+ 5 more
10 essays · combination
10⁻² 10⁻¹ 1 10¹ 10² 10³ 10⁴ ‖Ax − b‖ ‖x‖ the oracle discrepancy L-curve generalised scored against a truth none has oracle, relative error 0.11 discrepancy principle, as a multiple 1.1 L-curve corner, as a multiple 2.3 generalised cross-validation, as a multiple 1 the oracle needs the exact answer and is not a method it is the reference the others are scored on
Parameter choice
1
Choosing without knowing
2
Four knobs and one floor
3
A parameter chosen on a smaller problem
4
Thirty-two coefficients instead of a noise level
5
One draw in twenty
+ 3 more
8 essays · regularisation
0 8 16 24 32 40 48 56 64 0 0.25 0.5 0.75 1 index k filter factor fₖ no regularisation: fₖ = 1 truncation Tikhonov the same sum, three weights Tikhonov, relative error 0.11 truncation, relative error 0.11 no filter at all 5.5·10⁸ both filters are one expression with a different weight fₖ = 1 is the catastrophe
Regularisation
1
When the answer is a choice
2
Where the answer stops being in the data
3
A second blur, narrower than the first
4
Noise that spares the answer and fools the rules
5
The grid was the first filter
+ 3 more
8 essays · regularisation
the matrix 105 entries corner first — sparsest 227 entries, growth 1.9·10¹¹ largest first — safe 242 entries, growth 1.19 the middle factor is the smaller one, and its answer has no correct digits both factorisations reproduce the matrix ‖PA − LU‖/‖A‖, sparsest 3.8·10⁻¹⁷ ‖PA − LU‖/‖A‖, pivoted 5.4·10⁻¹⁷ forward error, sparsest 3·10⁻⁵ forward error, pivoted 4.8·10⁻¹⁶ red marks are entries elimination created the fill argument and the stability argument disagree
Sparse pivoting
1
Structure and stability stop being separable
2
A threshold between fill and growth
3
What the symbolic phase can only bound
4
The order that was right last time
5
An ordering that does not wait for the numbers
+ 3 more
8 essays · sparsity
10² 10².³ 10².⁵⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁶ 10⁻¹ 10⁻⁰.⁵ 1 rows in the sketch worst relative distortion dimension 64 dimension 256 5 seeds per point, band is best to worst the dimension does not appear
Sketching
1
The dimension does not appear
2
The sketch that is not the answer
3
The sketch that is spent
4
Built from products alone
5
Sketching what is never unfolded
+ 2 more
7 essays · randomised
chain · cheapest 1.51·10⁴ chain · greedy 5.06·10⁴ chain · dearest 5.13·10⁸ train-inner · cheapest 3344 train-inner · greedy 1.51·10⁴ train-inner · dearest 6.58·10⁹ als-step · cheapest 1.05·10⁵ als-step · greedy 1.13·10⁵ als-step · dearest 1.13·10⁵ multiply-adds, on a logarithmic scale one value, many prices chain, best ⁄ worst 3.4·10⁴ train, best ⁄ worst 2·10⁶ als step, best ⁄ worst 1.1 worst greedy excess 4.5 no answer changes and the price does
Contraction
1
The order the products are taken in
2
The plan that was right at rank four
3
A ceiling is not a target
4
The search that got worse as it widened
5
A beam ranked on what remains
+ 1 more
6 essays · cost
0 0.25 0.5 0.75 1 0 0.25 0.5 0.75 1 x u exact central differences upwind the oscillation is exact ‖Ax − b‖/‖b‖ for the central answer 4.6·10⁻¹⁸ values outside [0, 1] 16 worst excursion 0.52 the dashed lines are 0 and 1, which the equation guarantees no solver was involved
Convection
1
The stencil that is not symmetric
2
The diffusion that makes the answer exact
3
Exact along one axis
4
The direction the diffusion does not go
5
A different equation on every grid
+ 1 more
6 essays · iterative
how far is it from A to an orthogonal matrix? smaller is nearer · the polar factor minimises this in every unitarily invariant norm polar factor U 1.8554 QR, signs fixed 2.1265 QR as returned 3.8226 200 drawn at random κ = 10 polar factor 1.9 QR, signs fixed 2.1 QR as returned 3.8 best of 200 random 2.7 ‖A − QR‖ is the same either way and ‖A − Q‖ is not
Polar decomposition
1
The nearest orthogonal matrix
2
An iteration that only multiplies
3
A test with no answer in it
4
A rotation that comes back mirrored
5
Five precise points are five points
+ 1 more
6 essays · orthogonality
5 6 7 8 9 10 0 108 216 324 432 log₂ n stored per unknown dense weak: every off-diagonal block strong: only the admissible ones a constant per doubling strong, n = 512 6.8·10⁴ weak, n = 512 6.1·10⁴ dense, n = 512 2.6·10⁵ per doubling 26 relative compression error 3.8·10⁻¹⁰ the dense line doubles and the other two add a constant
Storage growth
1
The offset that moved the slope
2
The partition that does not move
3
Two knobs on one number
4
A second objective that is the first one doubled
5
A geometry setting that is a second accuracy
+ 1 more
6 essays · hierarchy
θx (frequency across x) θy 0 π/2 π 0 π/2 π the coarse grid's under 0.2 under 0.40 under 0.60 under 0.80 under 0.95 under 1.01 damping per sweep two routes smoothing factor, scanned 1 closed form 1 30×30 frequency cells the marker is the mode nothing removes
Anisotropy
1
A direction the smoother cannot see
2
Smoothing a whole line at once
3
Coarsening in one direction only
4
Aggregating what the matrix calls strong
5
How much direction there was to lose
5 essays · iterative
the problem you posed A = H10 b = A·(1, 2, …, 10) the problem it answered exactly A + δA, b + δb ‖δ‖ / ‖A‖ = 2.3·10⁻¹⁷ the answer you wanted x = (1, 2, …, 10), exactly the answer you got x̂, wrong by 2.7·10⁻⁴ relative backward error 2.3·10⁻¹⁷ forward error 2.7·10⁻⁴ κ = 1.6·10¹³ κ · η = 3.6·10⁻⁴, and the measured forward error is 2.7·10⁻⁴. The algorithm is not at fault. The problem is. H10, LU with partial pivoting residual and error differ
Backward error
1
The exact answer to a nearby problem
2
A small residual is not a small error
3
An accuracy that is a backward error
4
Three errors and one number
5
The fifth author
5 essays · error
0 8 16 24 32 40 1 10² 10⁴ 10⁶ 10⁸ 10¹⁰ 10¹² 10¹⁴ matrix size n growth factor max|u| / max|a| the 2ⁿ⁻¹ bound worst of 30 random median random Wilkinson's matrix sits on the bound 30 Gaussian matrices per size at n = 40: bound 5.5·10¹¹, worst 4.8
Growth
3
The bound that is never attained
4
The growth a boundary-value problem supplies
5
A worst case is as fragile as its margin
6
Noise the growth amplifies
7
A margin the factorisation records
5 essays · elimination
0 40 80 120 160 200 240 10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ iteration ‖e‖ ⁄ ‖e₀‖ in the A-norm measured κ bound 119 steps 40×40, spectrum spread evenly in log bound permits 1417
Krylov
1
The rate the condition number predicts
2
An orthogonalisation nobody calls one
3
One sequence and two recurrences
4
A Krylov space for a problem that is not linear
5
The answer that arrives when the space runs out
5 essays · iterative
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
-1 -0.582271 -0.164542 0.253186 0.670915 1.08864 1.50637 0 eigenvalue 4 negative 10 positive counted before it was formed positive 10 negative 4 at zero 0 innermost ratio 39 the zero block is a theorem and so is the count either side of it
Saddle-point systems
1
The zero that is not a missing entry
2
Two ways to remove a constraint
3
A minimum the Hessian cannot see
4
The shift that stops at the first right count
5
A constraint the count stops seeing
5 essays · constraint
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
1 11 21 31 41 51 93 111.365 129.731 148.096 166.461 probes taken running estimate of the trace normal ±1 one probe, no error the exact trace 99 ±1 variance, this matrix 0 ±1 variance, rotated 57 normal variance 545 the same spectrum in a general basis costs the ±1 probe its whole advantage
Trace estimation
1
Counting what cannot be looked at
2
Counting what is inside a circle
3
A rate that belongs to the matrix
4
The split nobody is in a position to choose
5
A rule that reads only its own probes
5 essays · randomised
All essays