Every essay — page 16
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 last digit is the cheapest
Every cost curve measured here has the same shape: the first digits are cheap and the last ones are not. One method inverts it. Doubling the work buys twice as many digits as the previous doubling did, so the price of a digit halves every time it is paid.
The recursion that was never told the memory
A blocked elimination has to be tuned to its fast memory, and tuned to one memory it costs up to 2.9 times the best at another. A recursive elimination splits the columns in half down to one and reads no memory size at all. On eight fast memories from 36 to 576 words it moves between 0.94 and 1.28 times the words of the best tuned block, with the same 585,200 operations and the same pivots — and on a machine with two caches it beats the block tuned to either cache on six machines of seven.
The block size a recursion still has
A recursive elimination is sold as having no block size, and every real one switches to plain loops below some width. Swept over that width, the traffic is a staircase with its steps at the halvings of n, and its cliff sits where the blocked elimination's does — the first panel wider than √M − 2 moves 1.53 to 4.47 times the words, on six memories of six. On three caches the innermost decides, and a third cache costs every tuned block up to 14 per cent and the recursion nothing.
A ceiling is not a target
Asked to hold the smallest possible intermediate, an evaluation order costs a median of 1.55 times the cheapest order's arithmetic. Asked to hold no more than that same amount, it costs 1.15. The two answers hold exactly the same number of numbers, and on one network they are 5.17 times apart in work.
The plan that was right at rank four
An evaluation order is chosen once and paid for thousands of times, and the dimensions it was chosen at are not the dimensions it runs at. Compiled at rank four and run at rank 256 it costs 8.01 times the order that rank deserves; compiled at 256 and run at 2 it costs 301 times. A one-line rule recomputed on arrival costs 2.92 and 1.11.
The search that got worse as it widened
Keeping two candidate orders instead of one removes a third of the cheapest-product rule's excess, and by eight it has removed all of it — the two greedy rules this field separated become the same rule. On twenty-four of sixty networks a wider search returns a dearer order than a narrower one, and it is the better rule that it more often makes worse.
A beam ranked on what remains
A beam over contraction orders ranked on cost so far returns a dearer order when it is widened on 24 of 60 networks. Rank it on cost so far plus the largest group still to be paired — a lower bound on what remains, and free — and that falls to 12, eleven of them from the original 24. Rank it on a stronger estimate that is not a bound and the count stays at 23, but only 10 are the same networks: the anomaly has moved, not gone. At nine tensors, where the unranked beam's median at width 8 was worse than at width 1, both rankings make widening pay again.
Widen the beam where the ranking is right
A beam that is wide at its first pairings and narrow at its last looks like the right shape, since the early commitments are the damaging ones. Measured, it is worse than no beam: at nine tensors a width of 16, 8, 4, 2 and then 1 prices 742 pairings and has a median of 1.263 against width 1's 1.062 for 120. The reverse shape — width 1 early, doubling to 16 at the end — prices 78 pairings on seven tensors and finds the exhaustive order on 37 of 60 networks, against 30 for a constant width of 4 at 161. A beam should be wide where cost so far is nearly the whole cost.
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.
The same program, twice
One vector of 4,096 numbers, one summation algorithm, one precision, twenty-six runs — and twenty-one different answers. Nothing in the program chose between them, every one of them satisfies the textbook bound, and the exactly rounded answer is not among them.
A bound every answer satisfies
The classical bound on a summation error is correct, it covers all twenty-six answers one vector produced, and it is 7,932 times larger than the difference between them. A statement true of every ordering cannot say which ordering you got.
Where the disagreement comes from
The error of a reduction is a walk whose step length is the spacing of the running total, not of the answer. That one sentence predicts the size of the disagreement to a factor of two, explains why dividing the work makes it smaller, and explains why the value cannot be predicted at all.
The vector that hides it
Every quick demonstration of a parallel sum uses positive numbers, and positive numbers are the one family where the effect is absent. Measured on six inner products this site already computes, the summation condition number runs from exactly 1 to 10¹⁷ — and the safe end is where nobody makes a decision.
The sum that cannot be wrong
Snap every addend to a common multiple before adding, and every partial sum is exact — so the order stops mattering, by construction rather than by luck. Four hundred permutations return one value where an ordinary reduction returns three hundred and three.
What determinism costs
Six ways to add up a vector, priced in operations per element and in accuracy. Nothing sits in the bottom left of the figure — an answer that is the same on every machine costs between three and twelve operations where an answer that is not costs one.
Accuracy and agreement are different properties
The most accurate policy on this site's summation figure returns 119 different answers, and the one that returns a single answer is four orders less accurate. Neither property implies the other, and the vocabulary has one word for both.
One multiply the compiler removed
A determinant whose value is exactly 1, computed as exactly 0 by the expression that is written down, and exactly 1 by the same expression with the multiply and the add fused. Both forms conform to IEEE-754, both are legal compilations of the same source, and nothing in the program says which one you have.
A matrix that is definite on one machine
Two hundred Gram matrices, two conforming builds, and twenty-six of them get different answers to "is this positive definite". The exact verdict, from determinants in BigInt rationals, says the fused build is right nine times and the other one seventeen.
A square that evaluates negative
(x − 1)⁶ evaluated near x = 1 comes out negative at 179 of 401 points on one build and 196 on another, and the two disagree about the sign at 98 of them. Neither is nearer the truth: both traces are made entirely of rounding.
A stopping test is a race
One matrix, one right-hand side, one tolerance, thirteen partition counts — and eleven different iteration counts between 674 and 690. Every run converged, every answer is right to the accuracy asked for, and what differs is the bill.
The tolerance that buys no agreement
Ask for four more orders of accuracy and you get them — the answers improve by a factor of 1.5 million. The ratio between the best and the worst run is 1.34, 1.48, 1.71 and 1.17 across the same sweep. The band falls and it does not close.
A rank that depends on the thread count
One 60 × 14 matrix, one threshold, seven partitionings of the inner products that build its Gram matrix — and numerical ranks of 12, 12, 12, 10, 10, 11 and 11. Not a digit of an answer: the number of columns a model built from this matrix would have.
The length that changes the kernel
A dot product's accuracy steps by a factor of 1.57 between 63 and 64 terms, on vectors drawn identically at both lengths. Nothing about the problem changes there. A library switches from one accumulator to four, at a constant in somebody else's source file.
What a regression test can ask for
The machine's own variation on one solve is 3.2·10⁻¹², and the smallest defect whose answers clear it is one part in 10¹². The tolerance exists, it is bracketed on both sides by a factor of 1.42, and it is neither zero nor the 10⁻⁸ that usually gets typed.
An inner product with no fixed sign
‖QᵀQ − I‖ is how this site turns "orthogonal" into a number, and across ten partitionings it moves by 2.4%. The entries it is built from are not so lucky: 125 of the 1,128 off-diagonal pairs take both signs, and one of them takes five different values including zero.