Three walks and one bound

The essay on the order terms are added in makes a remark in passing: the bound on a left-to-right sum is n·u, and the measured errors behave more like √n·u. It is one sentence, it is not the point of that essay, and it is the kind of observation that gets filed as a curiosity about summation.

Two other measurements in this collection have since produced the same number, in objects that share no arithmetic with a sum and none with each other. This essay is what happens when the three are put on one pair of axes.

The three #

A left-to-right sum. Terms added one at a time into a running total. The bound on the error after n terms is n·u·Σ|xᵢ|, and it is the bound every account of floating-point summation states first. The summands here are positive and exactly representable in the working precision, and the reference is the same sum accumulated in double — which is not merely better but exact, because 24-bit summands and at most 2¹⁵ of them need 39 bits and a double has 53.

Fitted over nine sizes from 64 terms to 32,768: slope 0.486.

A chain of rotations. A sliding window of 24 rows on 6 columns, one row added and one removed at every step by Givens and hyperbolic rotations, with the triangular factor never rebuilt from the data. The bound on the drift is linear in the number of steps. The reference is the Gram matrix formed in BigInt from integer parts, so it too is exact.

Fitted over two decades of step count: slope 0.554.

A residual recurrence. Conjugate gradients on a diagonal matrix with one small eigenvalue, where r ← r − αAp accumulates and nothing recomputes it. The bound is u·‖A‖·max‖x_j‖, linear in the largest iterate. The reference is ‖b − Ax‖ recomputed from the iterate, on a matrix whose products are exact.

Fitted over ten decades of iterate size: slope 0.507.

Why they are comparable at all, and only in one way #

Three numbers agreeing is worth nothing without saying what would have made them disagree, and there is a real difficulty here that the figure’s construction is about.

The three quantities are a relative error of a sum, a relative drift of a Gram matrix and a relative residual gap. They are not the same size, they are not in the same units, and there is no scaling that would make them so. Any drawing that put them on a shared absolute axis would be claiming a correspondence that does not exist.

What is comparable is the exponent. Each series is divided by its own first point, and each independent variable by its own first value, so all three start at (1, 1) and the only thing left on the page is how each one grows. The claim is about slopes and nothing else, and the figure is constructed so that no other claim can be read off it.

The spread of the three is 0.068, which is smaller than the distance from any of them to 1.

Why the bounds have to be linear #

The bounds are not wrong and it is worth being clear about why they say 1 rather than a half.

A bound is a statement about the worst case, and it is obtained by taking absolute values. If the kth operation contributes an error of size at most εₖ, the total is at most Σ|εₖ| — and that sum is linear in the number of terms because every term is counted with a plus sign. There is no way to obtain anything else while remaining a bound: a sequence of roundings could all point the same way, on some input, and a bound has to cover it.

What actually happens is that they do not. A rounding to nearest is as likely to be up as down, the errors are close to uncorrelated, and a sum of k of them of typical size ε is of size ε√k rather than εk. That is the central limit theorem doing the only thing it does, and it is why the same exponent appears in three mechanisms that share nothing else: the mechanism is the sign of the rounding, and every one of the three has roundings.

What the difference is worth #

A factor of √k is not a subtlety. It is the whole difference between a bound that is usable and one that is not.

• At 1,000 steps, a linear bound is 32 times the behaviour.
• At 10⁶ steps, it is a thousand times.
• At 10⁹, which is a long-running stream or a large time-stepping run, it is thirty thousand.

So a code sized against the bound is sized for an event that will not happen, and a code sized against the behaviour has no guarantee. Both readings are in use and both are defensible; what is not defensible is not knowing which one a number came from.

The measured version has one more property worth naming: it is not a bound, and it is not a theorem. It is what these three accumulations did on these inputs, and a different input distribution — summands of one sign, a drift that is systematic rather than random, an operator whose roundings correlate — would produce something else. The collection’s own summation essay measures exactly that: five ways of rounding the same sum, of which two rise like √n and the others do not.

The one that is not a walk #

The counterweight is in this collection already and it is the reason the finding is a finding rather than a truism.

Round towards zero instead of to nearest and the errors stop having signs: every one of them points the same way, the walk becomes a sum, and the growth becomes linear — which is exactly the bound. The essay on the direction the error leans measures it, and the difference between the two rounding modes on the same sum is the difference between the two slopes in this essay’s figure.

So the half is a property of unbiased rounding rather than of accumulation, and the bound’s 1 is attainable rather than merely conservative: it is what a biased rounding actually does. Three unrelated mechanisms agree at a half because all three are running the same unbiased arithmetic, and a fourth mechanism running biased arithmetic would sit on the upper line.

That is what makes the three-way agreement worth drawing. It is not that bounds are pessimistic; it is that this particular pessimism has a cause, the cause is in the arithmetic rather than in any of the three algorithms, and it can be removed by changing the arithmetic.

What a half predicts that a one does not #

There is a use for the exponent beyond arguing about bounds, and it is the reason it is worth measuring rather than quoting.

It says what a refresh period buys. If the drift after k steps grows like √k, then refactorising every m steps holds the worst drift at √m·u rather than at √k·u — so quartering the period halves the drift, and the relationship between what is spent and what is bought is a square root in both directions. Under a linear model the same arithmetic says quartering the period quarters the drift, which is four times more optimistic and would lead somebody to buy a much shorter period than they need.

The measured table on the sliding window is exactly that: never rebuilding gives 6.6·10⁻¹⁴, every five hundred gives 2.9·10⁻¹⁴, every hundred gives 5.7·10⁻¹⁵ and every twenty-five gives 2.2·10⁻¹⁶. From five hundred to twenty-five is a factor of twenty in the period and a factor of 132 in the drift — faster than a square root, because the shortest period is holding the drift near the floor rather than on the curve.

And it says when a run is long enough to care. A walk reaches a stated error at k steps where a sum reaches it at √k, so the crossover between “this never matters” and “this dominates” is at a different place by an amount that grows with the run. For the residual recurrence the practical statement is that the gap is invisible below iterates of about 10⁴ and nine orders wide at 10¹⁴, which is a range no single rule of thumb covers.

Both of those are quantitative uses of an exponent, and neither is available from a bound.

What follows for a long run #

Three practical readings, in order of how much they cost.

Do not size a buffer, a tolerance or an error budget from a linear bound without saying so. The bound is right and it is thirty thousand times pessimistic at a billion steps, which will either waste a great deal or, worse, make a design look impossible that is not.

Do not size one from the square root either, without saying that too. It is a measurement on unbiased arithmetic with uncorrelated errors, and any of those assumptions can fail — a stream with a trend, a fused multiply-add pattern that correlates the roundings, a rounding mode chosen for reproducibility rather than for accuracy.

And prefer the repair to either. All three of the accumulations in this essay have one, all three repairs are the same shape, and each costs a small bounded fraction of the work: recompute from the data at some period, and the error stops growing with the run length at all. Compensated summation for the sum. Refactorisation for the window. Residual replacement for the recurrence. What each buys is that the answer’s accuracy stops being a function of how long the program has been running, which is a much better property than a smaller exponent.

What the exponent is not #

Two readings are available from a figure of three lines at a half, and both would be wrong.

It is not a claim that errors are small. A walk of a million steps is a thousand roundings deep, and on an ill-conditioned problem that is amplified again by the condition number before anybody sees it. The exponent says how the error grows with the length of the run; it says nothing about how large it is, and the two questions have different answers on every problem in this collection.

And it is not a licence to ignore the bound. A bound is a guarantee and a fitted exponent is a description of some runs. A computation that has to be certified — the interval arithmetic in this site’s own proved-bound essays, say — cannot use a measured exponent for anything, because the whole value of a certificate is that it covers the case that did not happen. The exponent is for sizing and for reasoning about how a run scales; the bound is for promising.

Keeping those apart is the reason this essay reports both numbers for all three mechanisms rather than declaring the bounds pessimistic and moving on.

Why three and not thirty #

A reader entitled to be sceptical will ask why three measurements are enough to call something a mechanism, and the answer is that the number that matters is not three but the spread.

If the three had come out at 0.41, 0.55 and 0.68 they would be three unrelated numbers near a half and the honest report would be that each accumulation does its own thing. They came out at 0.486, 0.554 and 0.507, which is a spread of 0.068 — smaller than the width of any one of the three fits, and an order of magnitude smaller than the distance from any of them to the bound’s 1. Three quantities agreeing that closely, on axes that share no units and mechanisms that share no arithmetic, is not three data points; it is one prediction confirmed three times.

The prediction is also not this collection’s. It is the central limit theorem, applied to a sequence of independent roundings of comparable size, and it says a half exactly. What the measurements add is that the assumptions behind it — independence, comparable size, no bias — hold well enough in three real algorithms to produce the exponent to within seven per cent, which is a claim about numerical software rather than about probability.

Where those assumptions fail, the exponent goes with them, and the collection has that case too: a biased rounding mode makes the errors agree in sign and the walk becomes a sum. That is the fourth measurement and it is the one that makes the other three mean something.

What is asserted #

That each of the three fits a half, to within 0.12, on its own axes and against its own bound.

That the three agree with each other more closely than any of them agrees with its bound — a spread of 0.068 between them, against a distance of at least 0.45 from any of them to 1.

That every bound is linear in the quantity its measurement is fitted against, which is stated rather than fitted, because it is a property of how a bound is derived and not of any run.

And the refusal: each of the three assertions is fed the claim that its slope is 1, and each one fails. That is what makes the figure a comparison rather than an illustration.