Every essay — page 5
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.
A limit the matrix never reaches
Szegő's theorem gives a Toeplitz family's condition number in closed form — ((1+ρ)/(1−ρ))², which is 81 at ρ = 0.8. The 8×8 section reaches 52% of it, the 128×128 reaches 98.9%, and none of them ever arrives. A statement about a family is not a statement about the matrix in front of you.
A preconditioner that changes sign
Strang's circulant preconditioner takes Toeplitz conjugate gradients from 179 steps to 10 at n = 256. At n = 64 on the same family it takes 66 steps to 109 — worse than doing nothing. Between those rows the preconditioner's smallest eigenvalue crosses zero, and nothing in the published account of the method mentions that it can be negative.
The circulant that cannot be indefinite
The previous essay found a preconditioner taking 117 steps against an unpreconditioned 59, because its smallest eigenvalue was −0.173. Average the two diagonals instead of choosing between them and the count is 7, 8, 9, 10, 10 across a factor of sixteen in size.
Two dimensions, and the cluster that thins
The same kernel, the same averaging, the same transform — applied along two axes instead of one. In one dimension the preconditioned step count is 7, 10, 10, 10; on square grids with the same unknown counts it is 10, 18, 20, 21, and the share of the spectrum near one falls from 56% to 17%.
An equation whose unknown is a matrix
AX + XB = C is linear in X, so it has a coefficient matrix, and writing it down is the obvious thing to do. At n = 100 that matrix has a hundred million entries for a problem with ten thousand unknowns, and the algorithm everybody uses instead never forms it. Its conditioning is not the eigenvalue gap either, which is the number a reader is invited to consult.
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.
A bound that holds with probability
Every other guarantee on this site is deterministic. The randomised low-rank approximation offers one that holds with a probability, the seed changes the answer, and the honest figure is a band rather than a line.
The dimension does not appear
A random projection preserves the lengths of a set of vectors to within a distortion that depends on how many vectors there are and not on how many coordinates each one has. That is the fact the whole field rests on, and it is genuinely surprising.
Randomisation does not create structure
On a matrix whose singular values are all equal, a rank-ten randomised approximation has error 1.0 — and so does the optimal deterministic one. Neither achieved anything, and only one of them is usually sold with the implication that it might.
Counting what cannot be looked at
The trace is n additions and one of the most expensive quantities in the subject to estimate, because the matrices whose trace is wanted are never stored. Hutchinson's estimator is unbiased with one line of algebra — and its variance depends on which random vector is used, by a factor that is a property of the matrix, and on a diagonal matrix one choice is exact from the first probe and the other is not.
The sketch that is not the answer
Sketch-and-solve throws away the original problem and keeps the small one's answer, which is why its answer moves with the seed. Use the same sketch as a preconditioner instead and the condition number the iteration sees is the same number at every κ from a hundred to ten billion — identically the same, to nine digits, because the spectrum cancels out of it.
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.
A parameter that counts steps
The regularisation field's knob is a positive real number chosen by one of three rules. The iterative field's is an integer nobody called a knob — where to stop. On the same problem the best step is 20 and the best λ is 0.025, and they reach 0.1426 and 0.1406.
Four knobs and one floor
A truncation, a Tikhonov parameter, a step count and a randomised rank, on one problem with an answer that is known. Their best errors are 0.1445, 0.1406, 0.1426 and 0.1449 — a spread of 3% across four methods that share no arithmetic.
The part of a solver that may be rounded
A preconditioner computed and applied with a three-bit significand still returns thirteen correct digits — it costs seventeen extra iterations and nothing else. Round the working arithmetic instead and the step count barely moves while the answer loses exactly the digits the format dropped.
An answer that changes with the seed
A randomised rank-k solve is a truncation computed in a random subspace, and it reaches the same floor as the deterministic ones. What it does not do is return the same answer twice — a factor of 1.84 across four seeds at rank 8, and 1.02 at the rank where the method is best.
The step that stops mattering
Regularise the problem the iteration has built rather than the problem it was given, and the error curve stops turning. The unregularised run ends 1,127 times above its own best; the same run with a penalty inside it ends 1.000000000003 times above.
A parameter chosen on a smaller problem
Inside a hybrid method the regularisation parameter is chosen on a 25×24 problem rather than a 64×64 one. The rule that reads a residual transfers exactly; the rule that reads a trace is biased by exactly two grid steps at twenty-four steps and one at forty, at every noise level from 10% to 0.1%.
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.
The same arithmetic at a different price
A blocked and an unblocked elimination perform 72,568 operations each — the same operations, associated differently — choose the same pivots, and return a factorisation identical to the last bit: ‖PA − LU‖/‖A‖ = 4.487946226420872·10⁻¹⁶ in both. One of them moves 41,332 words between fast and slow memory and the other moves 19,476.
A block size is a property of the machine
Three lines of counting say the best block size is √(M/3). Scanned over every integer at five fast memories, the measured optimum is √M − 2 — exactly, at all five. The count has the right scaling and the wrong constant, low by a factor of 1.56, and the wrong form: the answer is affine in √M rather than proportional to it.
A reduction that changes the order
A tall-skinny QR computed as a tree of independent block factorisations touches a 512×12 matrix once instead of twelve times, computes a completely different sequence of roundings from the sweep it replaces, and returns ‖AᵀA − RᵀR‖/‖AᵀA‖ = 1.65·10⁻¹⁵ against the sweep's 9.95·10⁻¹⁵. On the same matrix classical Gram–Schmidt returns 4.6·10⁻¹⁰.
The message and the word
Three factorisations of one matrix on sixteen processors: 48 communication rounds, 4, and 4. The words sent are 1,170, 1,170 and 2,160 — so the method with the fewest rounds sends the most words, and the count that separates the three is the one no operation count can see.
Doing it twice
Cholesky QR squares the condition number — a fitted slope of 1.95 in κ against the Householder sweep's 1.00. Run the identical routine a second time on the Q it returned and the slope is 0.93, the orthogonality is at or below the sweep's at every κ, and the price is one more all-reduce.
Memory bought with messages
Holding four copies of the data instead of one is supposed to cut a matrix multiplication's communication by √4. Measured on a machine of 64 processors it costs 14% more traffic; at 576 it saves 44%, which is 72% of what the law promises. The memory is exactly four times, and that part is not asymptotic.