The fields
The arithmetic underneath
The representable numbers are spaced, and the spacing doubles at every power of two. Everything else follows from that: why subtracting two close numbers destroys the part you wanted, why the order of a sum changes its value, and why the mantissa is the one parameter on this site worth putting on a slider.
19 essays — What a float can hold, Cancellation takes the answer, not a digit, The order they are added in and 16 more
Two errors, and whose fault they are
A good algorithm returns the exact answer to a nearby problem. So a wrong answer has two possible authors, and they can be measured separately: the backward error says how well the algorithm did, the condition number says how much the problem amplifies it, and only their product is what anyone sees.
19 essays — The exact answer to a nearby problem, A small residual is not a small error, The condition number is an amplifier and 16 more
Elimination, and the swap
Gaussian elimination is the first algorithm anybody learns and the row interchange is the part nobody is given a reason for. Here it is run without one, on a matrix where that fails — quietly, returning an answer of the right shape — and the growth factor that governs the whole story is plotted against a bound it never attains.
18 essays — Elimination is a sequence of choices, The swap that is not optional, The bound that is never attained and 15 more
Orthogonality, measured
Orthogonal is not an adjective, it is a number: ‖QᵀQ − I‖. Two algorithms that are the same algebra written in a different order return 10⁻¹⁵ and 1 for it on the same matrix — and the one that fails still reconstructs the matrix perfectly, which is why nothing warns you.
18 essays — Orthogonal is a number, Two Gram–Schmidts, A reflection cannot stop being one and 15 more
Least squares, and the road not to take
The normal equations are taught first and used by nobody, because forming AᵀA squares the condition number and then, below a computable value of ε, breaks outright. Underneath that is a harder fact: a wide range of very different fits explain the data equally well, and no arithmetic can choose between them.
19 essays — The projection and the right angle, The road that squares the problem, The valley with no bottom and 16 more
Regularisation, and the answer that is chosen
Some problems do not determine their own answer. The data is consistent with a range of solutions that differ by orders of magnitude, no arithmetic can choose between them, and something outside the data has to. That choice is the computation rather than a preliminary to it — and every published rule for making it is a heuristic scored, here, against a truth that exists only because the problem was constructed.
18 essays — When the answer is a choice, Where the answer stops being in the data, Choosing without knowing and 15 more
Eigenvalues, singular values, rank
A symmetric matrix gives up its eigenvalues without complaint. An unsymmetric one can move them by the eighth root of a perturbation, so rounding error alone shifts them by a hundredth. And rank is not a property a floating-point matrix has — it is a decision about a gap, and the gap is worth printing beside it. The algorithm that libraries actually run lives here too, and it needs a shift before it is an algorithm at all.
32 essays — Symmetry is worth more than precision, Rank is a decision, The best approximation there is and 29 more
The eigenvalue problem that is not linear
A damped structure does not produce Ax = λx. It produces (λ²M + λC + K)x = 0, where the matrix whose null vector is wanted is a function of the number being solved for — so there is nothing to factorise, an n × n problem has 2n eigenvalues, and every algorithm anybody runs is an algorithm for something else. What that substitution costs is measurable: the linearisation is solved to the rounding level at every stop of a sweep across which the answer loses eleven orders.
20 essays — A matrix that depends on its own eigenvalue, A backward-stable answer to a problem nobody asked, The scaling that buys ten orders and 17 more
Reduction, and what a model is for
A state matrix is n × n and the thing anybody wants from it — the map from an input to an output — is a function of one complex variable. The gap between those two numbers is this field. A reduced model is an approximation of the function and not of the state, so its error is measurable as a norm of a function rather than as a residual, and one of the two ways of building it comes with a bound computable before the model exists. That bound turns out not to be an inequality: on ordinary problems it is attained. What makes any of it possible is that a Gramian's eigenvalues fall off a cliff, and the reason they do is a rational approximation problem with a closed-form rate.
18 essays — A model that is a rational function, The bound that is known in advance, The product nobody had to form and 15 more
Iterating, instead of factorising
At scale nobody factorises, and the reason is not accuracy — it is that the factors of a sparse matrix are not sparse. What replaces elimination is a sequence of approximations, and the question changes shape: not what the residual of the factorisation is, but how fast the error falls and whether the thing you can measure tracks the thing you cannot. On the model problem every rate is known in closed form before anything runs.
39 essays — The rate the condition number predicts, An orthogonalisation nobody calls one, Changing the condition number on purpose and 36 more
Sparsity, and what elimination costs
Eliminating a variable couples everything it touched to everything else it touched, and every one of those couplings is an entry that was zero in the matrix and is not zero in its factor. On the same matrix one elimination order gives a factor of a thousand entries and another gives ten thousand — the two factorisations equally accurate, one of them fitting in memory. Nothing numerical chooses between them.
18 essays — The factor is not sparse, The order decides the memory, Two ends of the same arrow and 15 more
Structure, and the solver that cannot see it
The sparsity field is about a matrix most of whose entries are zero. This is the other way a matrix can be small: a circulant is n numbers and a Toeplitz matrix is 2n − 1, and neither of them has a single zero entry, so nothing in the sparsity field applies. What the structure buys is an exact spectrum, a condition number in closed form and a solve in n log n — and what it does not buy is a well-conditioned problem, which is the half that gets summarised away.
18 essays — The matrix that is one row, A limit the matrix never reaches, A preconditioner that changes sign and 15 more
Neither sparse nor dense
There is a third answer to a matrix that is too large, and it is the only one whose cost you choose. Sparsity is handed over by the problem — an entry is zero or it is not — and an operator with no entries is handed over by the code. A kernel matrix has no zero entries, is described by no fewer numbers than it contains, and is cheap anyway, because the block between two clusters of points that are far apart is numerically low rank. Where you cut its singular values is a decision, so the storage is a function of the accuracy asked for rather than of the matrix; and the accuracy turns out not to be an accuracy at all, but a backward error chosen at the top of the program.
19 essays — A block nobody can call sparse, A rank that is a number of digits, The size the rank does not notice and 16 more
When the index is a tuple
A discretisation on a d-dimensional grid has n^d unknowns, so its matrix has n²ᵈ entries — a number with no physical meaning. What such a matrix usually is instead is a sum of d Kronecker products of n × n matrices, and nothing has been approximated: assembling it was the mistake. Then the same word is carried one step further, to arrays with three or more indices, and every theorem this site has relied on about rank stops being true. The best approximation may not exist, the rank depends on the field the entries are read over, and there is no decomposition that is orthogonal and diagonal at once. What survives is not the definition but the algorithm: take the SVDs of the reshapes, and existence, computability and a quasi-optimality factor all come back.
18 essays — An index that is a pair, A solve that is d decompositions, A nearest point that is not there and 15 more
The matrix that is a graph
Every matrix in the fields before this one arrives as a matrix. A graph does not: it arrives as vertices and edges, two different matrices can be built from it that answer different questions, and what anybody wants back is a partition, a ranking or a count — a discrete answer, computed by continuous arithmetic. So a rounding here does not make the answer slightly wrong, it makes it a different answer: a connected graph reported as two pieces, a leaderboard whose middle places are decided by one uncrawled link, a determinant that is known in advance to be a whole number and stops being one at sixteen vertices while the elimination that produced it stays backward stable throughout. Two things this field has that nothing else on the site does. The Laplacian's null vector is exact — the rows are cancellations of integers, so L·1 is zero rather than nearly zero. And there is a two-sided bound that is proved rather than estimated, from one matrix–vector product.
19 essays — A matrix with no numbers in it, Two Laplacians of one graph, The vertex nobody solves for and 16 more
Exact arithmetic, and what it costs instead
An integer matrix eliminated over the rationals commits no rounding anywhere, so the forward error is zero, the residual is the zero vector, and the identity the rest of this site is built on has nothing left to say. The cost does not disappear with the error — it moves into the length of the numbers, where three eliminations returning the same integer differ by four orders of magnitude in the widest one they form. What is left to decide is which route pays: divide by the previous pivot and stay in the integers, reduce every fraction and pay a gcd per operation, or work modulo primes where nothing can grow and put the answer back together afterwards.
18 essays — An answer with no error in it, Every intermediate is a minor, The answer is longer than the question and 15 more
Randomised, and the guarantee that changes kind
Every other claim on this site is deterministic: the residual is below a bound or it is not. A randomised low-rank approximation has an error bound that holds with a probability, and the seed changes the answer — so the figures draw a band rather than a line. What sketching buys is the same quality for fewer passes over the data, which is a statement about cost. On a matrix with no structure to find it buys nothing, and neither does anything else.
18 essays — A bound that holds with probability, The dimension does not appear, Randomisation does not create structure and 15 more
Methods that were designed apart
Every field here introduced its own knob and its own vocabulary, and the essays that did so were written as though the methods were alternatives. Put four of them on one problem with an answer that is known and they land within a few per cent of each other, because what each one controls is how much of the data to believe and how much is worth believing belongs to the problem. This field is what happens when two methods meet: which parts of a solver can be computed at three significand bits, which cannot be rounded at all, and where the reading that every knob is the same knob stops being true.
18 essays — A parameter that counts steps, Four knobs and one floor, The part of a solver that may be rounded and 15 more
When the problem arrives again
Every other field here solves one system and measures how wrong the answer is. Almost no computation is shaped like that: a solve is one step of an outer loop, and the vector it returns is an input rather than a deliverable. That changes what its accuracy is for. An outer iteration recomputes its residual from the matrix at every step, so whatever the inner solve got wrong is measured again rather than carried — and four quantities that looked like accuracy requirements turn out to be assets with a shelf life, priced here against a root that is known exactly.
19 essays — The problem that arrives again, The accuracy that is thrown away, A tolerance that reads its own residual and 16 more
Where the flop count stopped predicting the time
Every cost claim in the other eleven fields is a count of arithmetic, and those counts have not decided which of two implementations is faster for about thirty years. A blocked and an unblocked elimination perform the identical multiplications in a different order, return a factorisation identical to the last bit, and move a factor of two different amounts of data. What is counted here is words moved between a fast memory and a slow one, with the size of the fast memory named on every figure — because nothing in the model is optimal until it is.
18 essays — The same arithmetic at a different price, A block size is a property of the machine, A reduction that changes the order and 15 more
The answer that depends on the machine
Every other field here asks how wrong an answer is. This one asks how many answers there are. A parallel reduction adds a vector up in however many pieces there are workers, in whatever order they finish — so the same program, on the same data, at the same precision, returns a different number on a different machine, and every one of those numbers satisfies the published bound. The disagreement is a quarter of κu and the bound is ten thousand times larger, which is why nothing reports it. It matters where a number is compared to something: a stopping test, a rank test and a definiteness test each turn a real number into a verdict, and a verdict has no last digits for a disagreement to hide in. One matrix here has three different numerical ranks and one solve has thirteen different bills. And the smallest instance needs no parallelism at all — a multiply the compiler was allowed to fuse, which is one rounding, and which decides the sign of a determinant whose value is one.
20 essays — The same program, twice, A bound every answer satisfies, Where the disagreement comes from and 17 more
The matrix a constraint makes
Every difficult matrix in the other fields was difficult for a reason the arithmetic supplied: a Hilbert matrix arrives ill conditioned, a Wilkinson matrix grows under elimination, a kernel matrix is dense. Ask a problem to minimise something subject to a constraint and the matrix that results is difficult for a reason the algebra supplies. Its zero block is the second derivative of a Lagrangian with respect to its own multipliers, so no pivot order removes it and no precision changes that; its inertia is known before anything runs; and Cholesky does not fail somewhere on it, it fails at the first constraint row, on a number the problem already contained. Then the field's second surprise, which is the opposite one: an interior-point method drives the condition number of this matrix to 10¹⁵ deliberately, and the answer keeps fifteen digits — because the number that describes the error is not the one every library prints.
18 essays — The zero that is not a missing entry, Two ways to remove a constraint, Three eigenvalues, and two are the golden ratio and 15 more
Every essay, with its figures · The threads that cross the fields · The depth ladders