Every essay — page 8
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.
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.
Where the format starts paying
A hierarchical solve costs 1.48 times a dense factorisation at 64 unknowns and 0.16 times it at 512. The crossover is between 64 and 128, it walks right when the accuracy is tightened, and the exponent between consecutive sizes is 2.13, 1.93, 1.74 — falling towards one and never arriving.
The order the products are taken in
The sparsity field's first essay says the elimination order decides the memory. This is the same sentence about arithmetic: a contraction of several tensors over shared indices has one value and many evaluation orders, and on the inner product of two trains they differ by a factor of two million.
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.
The zero that is not a missing entry
A constrained minimisation produces a matrix with a zero block, and the zero is a theorem rather than a sparsity pattern. No pivot order makes it positive definite, no precision changes that, and Cholesky does not fail somewhere on it — it fails at the first constraint row, on a number the problem already contained.
Two ways to remove a constraint
A constrained system can be reduced by eliminating the multipliers or by eliminating the constrained directions. Both give the same answer in exact arithmetic and inherit different condition numbers — one of them squares the constraint's, and the other does not contain it at all.
Three eigenvalues, and two are the golden ratio
Precondition a saddle-point system by the block diagonal of its own two definite pieces and the preconditioned matrix has exactly three distinct eigenvalues — 1, and the two roots of λ² − λ − 1. A minimal polynomial of degree three means three steps, at every conditioning, and the preconditioner nobody can afford turns out to be the statement the affordable ones are measured against.
A preconditioner that need not know the constraint
Keep the constraint block exactly and replace the objective block by anything positive definite on the null space. The preconditioned matrix then has 2m eigenvalues at exactly one, and its remaining n − m are the generalised eigenvalues of a pencil in which the constraint does not appear. Sweep its condition number over six decades and they do not move in six digits.
A condition number sent to infinity
An interior-point method manufactures an ill-conditioned matrix on every iteration, deliberately, because the separating of a diagonal is how it discovers which constraints are active. Written one way the answer keeps fifteen digits at a condition number of 3·10¹⁵. Written the other way — the way almost every code writes it — it has none left.
The regularisation that legalises every order
Perturb a saddle-point matrix's two blocks in opposite directions and it acquires a factorisation with a diagonal D under every symmetric permutation — not under a good one, under all of them. Five hundred random orderings, five hundred successes, and a growth factor that spans six orders across them.