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
+ 16 more
21 essays · combination
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
+ 11 more
16 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
+ 8 more
13 essays · sparsity
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
+ 6 more
11 essays · regularisation
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
+ 6 more
11 essays · hierarchy
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
+ 6 more
11 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
+ 4 more
9 essays · cost
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
5
A floor with a cliff at one
+ 4 more
9 essays · sequence
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
+ 4 more
9 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
+ 4 more
9 essays · randomised
1 10¹ 670 673 676 679 682 685 688 691 694 pieces the inner products were summed in iterations to the tolerance 674, the cheapest run 690, the dearest the same solve, priced partitionings run 13 distinct counts 11 spread, per cent 2.4 best forward error 6.3·10⁻¹¹ worst 1.1·10⁻¹⁰ one matrix, one tolerance and the cost is the machine's
Stopping test
1
A stopping test is a race
2
The tolerance that buys no agreement
3
The reading that never moves
4
The honest residual is not a stopping test
5
Five steps is a rate
+ 4 more
9 essays · machine
10¹ 10² 10² size n condition number limit 81 measured a limit, as a fraction of itself reached at n = 128 0.99 still to go 0.011 κ at n = 8, as a fraction 0.52 every point is below the line and none of them is on it the limit is not a value
Toeplitz
1
A limit the matrix never reaches
2
The circulant that cannot be indefinite
3
Two dimensions, and the cluster that thins
4
Four orders of conditioning, and four steps
5
The staircase a separable kernel builds
+ 4 more
9 essays · structure
10² 10³ 10⁴ 10⁵ matrix size n count operations, both words, unblocked words, blocked (b = 6) the answer does not move ‖PA − LU‖/‖A‖, unblocked 2.8·10⁻¹⁶ ‖PA − LU‖/‖A‖, blocked 2.8·10⁻¹⁶ difference between them 0 the dashed curve is both orderings' operation count the solid pair is what they cost
Blocking
1
The same arithmetic at a different price
2
A block size is a property of the machine
3
The recursion that was never told the memory
4
The block size a recursion still has
5
The leaf that sits on the edge
+ 3 more
8 essays · cost
1 10¹ 10² 10³ 10⁴ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² 10¹ sweep relative error, and the largest term's size rising: the swamp's largest rank-one term falling, slowly: its error falling, once: a fit with an answer a plateau with a rising floor swamp error 0.0014 swamp term 10 term growth 2.2 benign error 9.7·10⁻¹⁵ benign term growth 1 the error alone cannot tell the size of the terms can
Alternating least squares
1
An iteration that walks out of the set
2
The test that is a deadline
3
The repair that costs exactly itself
4
One term too many
5
The rank a sweep can vouch for
+ 2 more
7 essays · tensor
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
5
An augmentation read in the smallest eigenvalue
+ 2 more
7 essays · constraint
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
4
A curvature direction the factors cannot refine
5
The push a pivot needs belongs to the matrix
+ 2 more
7 essays · elimination
0 2 4 6 8 10 12 14 16 10⁻¹ 1 index k λ the transform the eigensolver C = F* Λ F is a factorisation worst relative disagreement 2.6·10⁻¹⁵ ‖Cx − b‖/‖b‖ from the transform solve 4.7·10⁻¹⁶ imaginary part of a real spectrum 1.2·10⁻¹⁶ n = 16, and the whole matrix is 16 numbers eigenvectors known in advance
Circulant
1
The matrix that is one row
2
The circulant the problem did not contain
3
Two near-zeros cost less than one
4
The correction lost to its own two-by-two solve
5
A zero no twist can step around
+ 2 more
7 essays · structure
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
5
A multiplier is a force
+ 2 more
7 essays · leastsquares
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
6
The residual the appended block cannot remove
+ 2 more
7 essays · orthogonality
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
+ 2 more
7 essays · elimination
All essays