Numerical Linear Algebra
where the algebra stops being the arithmetic
Field

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.
110¹10⁻¹¹10⁻⁸10⁻⁵pieces the vector was divided intodistance from the exact sum, relativethe published boundκ · uone vector, one algorithmdistinct answers21runs26spread, in ulps2.3·10⁷κ of the sum10⁸bound ÷ worst error2.6·10⁴nobody chose pand no answer is the answer

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.

 10²10⁴10⁶10⁸10¹⁰10¹²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹κ of the sumrelative sizethe boundκ · umeasured spreadtwo curves and one constantspread ÷ κu, low0.25spread ÷ κu, high0.26bound ÷ spread, low7932decades swept10the spread is computablethe bound cannot see the order

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.

 051210241536204810⁻¹⁷10⁻¹⁴terms consumederror accumulated so farone accumulator8 piecesthe steps are the partial sumspeak partial sum32the answer1.6·10⁻⁵error, one piece7.6·10⁻¹⁴error, 8 pieces2.4·10⁻¹⁴mean at p = 648.1·10⁻¹⁵the walk sets the sizeand nothing sets the value

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.

 κ of the suma component of b − Ax1.01·10¹⁷ad − bc, near-degenerate3.6·10¹⁶qᵢᵀqⱼ, an orthogonality check7.39·10¹⁵pᵀAp, a curvature409zᵀAz, a trace probe41.8rᵀr, a residual norm1measured, not assumedhighest10¹⁷lowest1above 10¹⁰3terms64sums of squares are safeand nobody decides anything from one

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.

 distinct answersone accumulator303eight pieces72compensated119pre-rounded1exact1worst error 1.17·10⁻⁸worst error 4.61·10⁻⁹worst error 4.96·10⁻¹⁰worst error 4.91·10⁻⁶worst error 0bitwise, or not at allpermutations400one accumulator303pre-rounded1its error4.9·10⁻⁶compensated error5·10⁻¹⁰accuracy and agreement are different propertiesand the accurate one is not the agreed one

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.

 02468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸binary64 operations per elementrelative errorruntime orderfixed partitionpre-rounded, one passpre-rounded, two passescompensated (Kahan)exact accumulationwhat determinism costsreproducible policies3cheapest, ops/element3its error2.3·10⁻⁷two passes10⁻¹⁷ordinary, 8 pieces2.7·10⁻¹¹nothing is cheap and exactthe middle of the figure is the answer

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.

 02468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²binary64 operations per elementrelative errorruntime orderfixed partitionpre-rounded, one passpre-rounded, two passescompensated (Kahan)exact accumulationwhat determinism costsreproducible policies3cheapest, ops/element3its error0.0024two passes10⁻¹⁷ordinary, 8 pieces3.6·10⁻⁷nothing is cheap and exactthe middle of the figure is the answer

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.

 2022242628303210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²k, where the entries are near 2ᵏrelative error of the determinantas writtenfused: exactproducts need 54 bitsone rounding, the whole answertrue determinant1naive, k = 300fused, k = 301first wrong at k27sizes returning 06both forms conformand the source does not say which

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.

 -12-11-10-9-8024681012log₁₀ of how nearly dependent the columns areverdicts that disagreed, of 40724103which one is correctmatrices tested200verdicts disagreed26fused was right9unfused was right17lower part: thefused build was righta sign has no last digitso a verdict has nowhere to hide

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.

 -101-101(x − 1) ÷ 0.001p(x) ÷ 2.68·10⁻¹⁵a square, drawn negativepoints sampled401negative, unfused179negative, fused196signs disagree at98widest gap1.4·10⁻¹⁵unfusedfusedthe true valuethe true curve is the flat oneeverything else is rounding

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.

 110¹670673676679682685688691694pieces the inner products were summed initerations to the tolerance674, the cheapest run690, the dearestthe same solve, pricedpartitionings run13distinct counts11spread, per cent2.4best forward error6.3·10⁻¹¹worst1.1·10⁻¹⁰one matrix, one toleranceand the cost is the machine's

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.

 -12-10-8-610⁻¹³10⁻¹¹10⁻⁹10⁻⁷log₁₀ of the residual tolerance asked forforward error of the answer1.34×1.48×1.71×1.17×the band does not closetolerances swept4runs at each7accuracy gained1.5·10⁶ratio at 10⁻⁶1.3ratio at 10⁻¹²1.2the bars falland they keep their height

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.

 13579111310⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹index ksingular valueσ₁ · 10⁻¹⁴, the thresholdone matrix, three rankspartitionings7lowest rank10highest rank12threshold7.3·10⁻¹⁴σ₁7.3the curves separate in the noiseand the threshold is drawn through it

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.

 5860626466687010⁻¹⁷10⁻¹⁶terms in the dot productmean relative errorthe kernel changes herea constant in a libraryone accumulator3.2·10⁻¹⁷four accumulators2.1·10⁻¹⁷step at the cutoff1.6cutoff64the problem did not changethe loop did

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.

 -15-13-11-910⁻¹³10⁻¹¹10⁻⁹10⁻⁷log₁₀ of the defect, relative to the entry it sits inhow far the answer movedthe machine, on its owna tolerance with two sidesmachine band3.2·10⁻¹²smallest caught10⁻¹²its nearest run4.6·10⁻¹²defects hidden3window, factor1.4below the band nothing is visibleand above it everything is

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.

 110¹-101pieces the inner product was summed inqᵢᵀqⱼ ÷ 2.78·10⁻¹⁷the true valuethe norm and its partsdistinct values5of runs10pairs with no fixed sign125of pairs1128κ of this inner product1.1·10¹⁷‖QᵀQ − I‖ moves by1the aggregate is stableand no entry of it is

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.

 00.10.20.30.40.50.60.70.80.9110⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹decay rate of the spectrumrelative spread of the rank-k errorthe seedthe machinetwo kinds of variationseeds drawn8partitionings7seed spread0.31machine spread9.8·10⁻¹⁶ratio3.1·10¹⁴one of these is recordedand it is the large one

The variation that comes with a seed

A randomised low-rank approximation's error moves by 31% between draws and by 10⁻¹⁵ between partitionings of one draw. In the one field on this site whose answer already comes as a band, the machine is inside the width of the line — and it is still there.

 κ of the suma component of b − Ax8.09·10¹⁷ad − bc, near-degenerate3.6·10¹⁶qᵢᵀqⱼ, an orthogonality check3.26·10¹⁶zᵀAz, a trace probe95.7pᵀAp, a curvature73.7rᵀr, a residual norm1measured, not assumedhighest8.1·10¹⁷lowest1above 10¹⁰3terms128sums of squares are safeand nobody decides anything from one

Two machines, one certificate

Nothing a solver returns says which of its answers you got. Four things could be reported instead — the summation condition number, the partition count, an exactly accumulated residual and a directed-rounding interval — and each costs about one pass over data the routine already has in hand.

All essays