Skip to content
1 6 11 16 21 26 31 36 10⁻²² 10⁻¹⁹ 10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ vertex, clique first then tail |entry| relative to the largest one rounding of the largest entry a bound that is proved Perron root 11 bracket, low 11 bracket, high 11 bracket width 1.2·10⁻⁴ smallest entry -1.5·10⁻²⁰ entries below zero 4 every entry is positive and the picture disagrees
Perron frobenius
1
An eigenvector that must not change sign
2
A ranking whose order is not determined
3
No subtraction, and no waiting
3 essays · graph
[ ε 1 ; 1 1 ] x = [ 1 ; 2 ], exact answer (1.000000, 1.000000) with partial pivoting 1 1 0 1 U after elimination 1.000000 1.000000 computed x backward error 0 forward error 0 without 10⁻¹⁷ 1 0 -1·10¹⁷ U after elimination 0.000000 1.000000 computed x backward error 0.25 forward error 0.71 no error is raised growth 10¹⁷
Pivoting
2
The swap that is not optional
3
The pivot that reads the units
4
A pivot that searches one row and one column
3 essays · elimination
0 5 10 15 20 25 30 35 40 10⁻¹¹ 10⁻⁹ 10⁻⁷ 10⁻⁵ 10⁻³ 10⁻¹ iteration ‖r‖ / ‖b‖ plain CG IC(0) CG what the preconditioner did κ(A) 48 κ(L⁻¹AL⁻ᵀ) 5.1 ‖A − LLᵀ‖/‖A‖ 0.083 2D Laplacian, n = 100 √κ ratio predicts 3.07×
Preconditioning
1
Changing the condition number on purpose
2
A preconditioner that changes sign
3
A speedup with a ceiling of its own
3 essays · iterative
0 14 28 42 56 70 84 98 10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² iteration change between iterates two rates, one curve α 0.85 λ₂(P) 0.9 predicted rate 0.77 measured 0.77 iterations 108 against the solve 10⁻¹⁶ the upper dashed line is αᵏ the curve is on the other one
Random walk
1
A ranking that is an eigenvector
2
The rate is the second eigenvalue
3
A chain with no stationary vector
3 essays · graph
0 8 16 24 32 1 1.1 1.2 1.3 1.4 terms added, each followed by a truncation error ⁄ best rank-k error optimal terms with nothing in common a subspace that drifts the rounding nobody should have feared drifting, worst excess 1 independent, worst excess 1 a linear bound would say 32 energy discarded, first 1.8·10⁻⁷ energy discarded, last 0.03 thirty-two roundings and four per cent
Recompression
1
The rounding that was not the problem
2
The count that is not the budget
3
A knob calibrated in residuals
3 essays · hierarchy
1 10¹ 10⁻¹¹ 10⁻⁸ 10⁻⁵ pieces the vector was divided into distance from the exact sum, relative the published bound κ · u one vector, one algorithm distinct answers 21 runs 26 spread, in ulps 2.3·10⁷ κ of the sum 10⁸ bound ÷ worst error 2.6·10⁴ nobody chose p and no answer is the answer
Reduction order
1
The same program, twice
2
A bound every answer satisfies
3
Where the disagreement comes from
3 essays · machine
1 2 3 4 5 6 7 8 10⁻¹⁷ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² 10¹ singular value, largest first relative error one-sided Jacobi zero-shift QR shifted QR eigenvalues of BᵀB against a rational bisection σₘᵢₙ, exactly 2.1·10⁻³⁰ worst, one-sided Jacobi 4.4·10⁻¹⁶ worst, zero-shift QR 2.2·10⁻¹⁶ worst, eigenvalues of BᵀB 1 a relative error is a ratio and the denominator is the answer
Relative accuracy
1
Small compared to what
2
Accurate is not a property of a method
3
A threshold the matrix does not set
3 essays · spectra
distinct answers one accumulator 303 eight pieces 72 compensated 119 pre-rounded 1 exact 1 worst error 1.17·10⁻⁸ worst error 4.61·10⁻⁹ worst error 4.96·10⁻¹⁰ worst error 4.91·10⁻⁶ worst error 0 bitwise, or not at all permutations 400 one accumulator 303 pre-rounded 1 its error 4.9·10⁻⁶ compensated error 5·10⁻¹⁰ accuracy and agreement are different properties and the accurate one is not the agreed one
Reproducible summation
1
The sum that cannot be wrong
2
What determinism costs
3
Accuracy and agreement are different properties
3 essays · machine
0 14 28 42 56 70 84 98 112 10⁻²² 10⁻¹⁸ 10⁻¹⁴ 10⁻¹⁰ 10⁻⁶ 10⁻² conjugate gradient iteration relative residual the unit roundoff, 1.11·10⁻¹⁶ the answer's residual the residual reported two residuals, one run reported, at its best 6.9·10⁻²¹ the answer's, at its best 5.1·10⁻¹⁰ unit roundoff 1.1·10⁻¹⁶ largest iterate on the way 9.3·10¹³ iterations drawn 110 the recurrence remembers every rounding and the stopping test is written in it
Residual gap
1
The residual the method reports
2
The number that is re-derived
3
A walk needs a length
3 essays · iterative
0 2 4 6 8 10 1 10² 10⁴ 10⁶ 10⁸ 10¹⁰ 10¹² spread of the row units (decades) condition number κ∞(DA) cond(DA) Hilbert κ∞ Hilbert cond one system, two numbers κ∞ at no spread 9.8 κ∞ at 10 decades 1.9·10¹⁰ cond, either end 7 Hilbert, equilibrated 1.3·10¹⁰ the solution is the same at every spread and one of these curves knows it
Scaling
1
The units the matrix is measured in
2
A condition number scaling cannot move
3
Two condition numbers of one matrix
3 essays · error
0 4 8 12 16 20 24 10⁻² 10⁻¹ 1 vertices on the smaller side conductance of the prefix cut 0.00752, the best prefix the rounding step λ₂ 0.14 cuts considered 23 best conductance 0.0075 at k = 12 worst prefix 1 the dashed curve is the eigenvector the solid one is what it costs
Spectral partition
1
The vector that has to be rounded
2
A bound with a square root in it
3
A partition decided in the last digit
3 essays · graph
10¹ 10² 10³ 10⁴ 10⁵ 10⁶ 10⁻⁹ 10⁻⁷ 10⁻⁵ 10⁻³ 10⁻¹ number of terms added relative error against the exact sum in order in a tree compensated binary32 · terms are 1/i compensated: 3·10⁻⁸
Summation
2
The order they are added in
3
Three walks and one bound
4
The vector that hides it
3 essays · arithmetic
0 0.25 0.5 0.75 1 10⁻¹ 1 10¹ share of the noise placed in the matrix least-squares error ÷ total least-squares error equally accurate total least squares ahead ordinary least squares ahead the model, not the method advantage, all noise in b 0.28 advantage, all noise in A 2.5 seeds at each share 40 the same total noise at every point and only where it sits changes
Total least-squares
1
When the matrix is wrong too
2
The two numbers a caller has
3
A unit is a statement about the noise
3 essays · leastsquares
58 60 62 64 66 68 70 10⁻¹⁷ 10⁻¹⁶ terms in the dot product mean relative error the kernel changes here a constant in a library one accumulator 3.2·10⁻¹⁷ four accumulators 2.1·10⁻¹⁷ step at the cutoff 1.6 cutoff 64 the problem did not change the loop did
Algorithm selection
1
The length that changes the kernel
2
The licence is not the boundary
2 essays · machine
2 3 4 5 6 7 10⁻¹⁷ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² poles in the approximant residuals and error forward error ‖T(λ)x‖ ‖T̃(λ)x‖ one extra evaluation against the approximant 1.5·10⁻¹² against the problem asked 1.9·10⁻⁶ forward error 4.8·10⁻⁵ ‖g − r‖ there 8.5·10⁻⁵ the free residual is flat and the answer is not
Approximation before linearisation
1
The problem the solver was actually given
2
An error committed before the arithmetic
2 essays · polynomial
half a step the 32 values of one block, in the order they arrive step 0.0625 one scale, thirty-two values octaves inside the block 1.9 entries rounded to zero 0 worst error over its bound 1 31 levels either side of zero the largest entry chose the step
Block formats
1
One exponent for thirty-two numbers
2
A bit buys an octave
2 essays · arithmetic
10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 1 10⁻¹⁷ 10⁻¹⁴ 10⁻¹¹ 10⁻⁸ 10⁻⁵ 10⁻² 10¹ x relative error of the computed value (1 − cos x)/x², as written 2 sin²(x/2)/x² no digits left at all binary64 throughout one function, two spellings · zero below 1.5·10⁻⁸
Cancellation
1
Cancellation takes the answer, not a digit
2
The formula sets the power, the sum sets the constant
2 essays · arithmetic
1 2 3 4 5 6 7 8 9 10 11 12 10⁻¹³ 10⁻¹¹ 10⁻⁹ 10⁻⁷ 10⁻⁵ 10⁻³ 10⁻¹ 10¹ order of the reduced model worst relative error a model made of measurements samples used 24 degree read 6 gap at the cut 2·10⁸ best model, order 12 its error 2.7·10⁻¹¹ states in the original 40 filled: at its own samples open: everywhere else
Data-driven realisation
1
A model with no matrices behind it
2
An error estimate made of samples
2 essays · reduction
does this matrix look nearly singular? green: the test agrees with the truth · red: it does not · the bar under each number is its magnitude, over sixty-two decades |det A| |det A|^(1/n) σₘᵢₙ 1/κ = σₘᵢₙ/σₘₐₓ 0.1·I at n = 40 perfectly conditioned 10⁻⁴⁰ 0.1 0.1 1 κ = 10¹⁰, |det| = 1 nearly singular 1 1 10·10⁻⁶ 10·10⁻¹¹ Hilbert at n = 8 nearly singular 2.7·10⁻³³ 8.5·10⁻⁵ 1.1·10⁻¹⁰ 6.6·10⁻¹¹ the two counterexamples κ of the scaled identity 1 its determinant 10⁻⁴⁰ κ of the normalised matrix 10¹⁰ its determinant 1 det(cA) = cⁿ det(A) so a determinant carries the units n times over
Determinant
1
The number that decides nothing
2
A rule that is correct and unusable
2 essays · error
Re λ Im λ what survives the arrows vertices 18 arcs 18 worst row sum 0 worst column sum 0 largest |Im λ| 0.98 asymmetry 1 the null vector is still exact and nothing else about the spectrum is real
Directed laplacian
1
A Laplacian that is not symmetric
2
A conductance the arcs do not measure
2 essays · graph
All essays