The honest residual is not a stopping test

The reading that never moves ran preconditioned conjugate gradients thirty times — five Laplacian grids from 36 to 196 unknowns, six working precisions from 53 significand bits down to 8 — and found the residual each run stopped on pinned between 1.10·10⁻¹³ and 9.95·10⁻¹³ while the error spanned eleven orders of magnitude. The residual a run reports is the one its recurrence carries, computed in the same reduced arithmetic as the iteration, and it can be driven to any tolerance without the answer approaching anything.

Its closing recommendation was a repair. Recompute $\lVert b - A\hat{x}\rVert/\lVert b\rVert$ in double from the matrix and the right-hand side, and the number tracks the error across the whole sweep: “One product with A in double, once every few steps, restores the eleven orders of resolution the recurrence threw away.” The essay used it as a report — computed at the end of each run. The obvious next step is to use it as the test: check it every few steps, and stop when it falls below the tolerance.

That figure is the problem in one picture: the reported residual flat along the bottom at the tolerance, and the error climbing with the unit roundoff from $1.4\cdot 10^{-13}$ in double to $6.0\cdot 10^{-3}$ at 8 bits. The earlier essay’s repair put a third line on it, the residual recomputed in double, which climbs with the error. Reading that line at the end is cheap and correct. Stopping on it is the question.

That step breaks the solver. And the repair for the repair is one clause.

Four ways to stop the same run #

The problem is the earlier essay’s: the two-dimensional Laplacian on a k × k grid, k = 6, 8, 10, 12 and 14, preconditioned by incomplete Cholesky with no fill, the right-hand side a fixed sine pattern and the reference answer a dense solve in double. The working arithmetic — products with A, inner products, vector updates — is rounded to 53, 32, 24, 16, 11 or 8 significand bits; the preconditioner is applied exactly.

A conjugate-gradient iterate does not depend on when the run will stop, so each of the thirty configurations is run once, to a cap of 300 steps, with the residual recomputed in double at every step; each stopping rule is then read off the same run, and the iterate at the step it chose is recomputed for its error. The four rules, all at a tolerance of $10^{-12}$:

The recurrence — stop when the run’s own residual falls below the tolerance, which is what the earlier essay measured. The honest residual, waited for — recompute the residual in double every five steps and stop when it falls below the tolerance. The honest residual, or stagnation — the same, or stop when two checks in a row each fail to halve it. The oracle — stop at the step of least error, which no run can know.

Each check of the double residual is one product with A, computed in double from the current iterate, and is counted as one product like any other.

Waiting for it never ends #

The figure at the top of the page is the products each rule spends, the median over the five grids, at each working precision.

In double the honest test behaves like the recurrence’s. The double residual and the recurrence’s agree to three digits there, as the earlier essay found, and the honest test is met at 15 to 25 steps — a check or two after the recurrence’s — for 18 to 30 products.

Below 53 bits it is never met. Not on one of the twenty-five runs. The double residual falls with the recurrence’s for the first ten or fifteen steps and then stops falling, at a floor set by the working precision — between $5\cdot 10^{-10}$ and $2\cdot 10^{-9}$ at 32 bits, $10^{-7}$ and $5\cdot 10^{-7}$ at 24, $2\cdot 10^{-5}$ and $10^{-4}$ at 16, $7\cdot 10^{-4}$ and $3\cdot 10^{-3}$ at 11, $5\cdot 10^{-3}$ and $2\cdot 10^{-2}$ at 8, depending on the grid — and no number of further steps moves it. A run that waits for it to reach $10^{-12}$ continues until something else stops it: on ten of the twenty-five, the 300-step cap; on the other fifteen, its own recurrence residual, which keeps falling geometrically in the reduced arithmetic until it underflows and the iteration breaks down, with no curvature left to divide by. Those runs end between 145 and 275 steps. Over all thirty runs the honest test costs 7,694 products against the recurrence’s 605.

The run on the 10 × 10 grid at 16 bits shows the shape. The recurrence’s residual crosses $10^{-12}$ at step 20 and keeps falling, to $4\cdot 10^{-163}$ by the end. The double residual reaches $8.89\cdot 10^{-5}$ at step 10 and is the same to three figures at every step after it: the iterate has stopped changing, because every update the recurrence still computes is smaller than the spacing of 16-bit numbers at the size of x. The error reaches $2.2\cdot 10^{-5}$ by step 10 and does not improve after that. A rule that waits for the double residual is waiting for something the arithmetic cannot produce, and it waits for 266 steps, until the recurrence underflows.

This is the earlier essay’s finding turned around. There the recurrence’s residual was a number that could be driven to the tolerance without meaning anything; here the honest residual is a number that means something and cannot be driven to the tolerance at all. Neither is a stopping test on its own. The first stops in the right place for the wrong reason; the second never stops.

Why the iterate stops moving #

The flat double residual is not noise sitting on a floor; it is a number that has stopped changing. On the 10 × 10 grid at 16 bits it reads $8.89\cdot 10^{-5}$ at step 10 and the same three figures at step 266. The reason is in the update $x \leftarrow x + \alpha p$. In reduced arithmetic an addition whose increment is smaller than half the spacing of representable numbers at the size of $x$ returns $x$ unchanged, and at 16 significand bits half that spacing is about $1.5\cdot 10^{-5}$ of $x$. The same threshold at 53 bits is $10^{-16}$, which is why the effect is invisible in double: the recurrence’s corrections stay above it until long after the tolerance is met. Once the recurrence’s steps have shrunk below that, every one of them is absorbed: the recurrence goes on computing smaller and smaller corrections, its own residual goes on falling because it is updated by the same tiny amounts, and the iterate, which is the only thing anyone wanted, does not move.

That is why the error tracks the unit roundoff to a factor of 1.5 across the sweep, as the earlier essay measured: the iterate is the exact answer rounded to the working format, give or take what the last absorbed updates would have changed. And it is why no amount of further iteration helps. A small residual is not a small error made the general case that the two quantities differ by a condition number; here, below the floor, they are not even computed from the same object — the recurrence’s residual describes a sequence of updates that never reached $x$.

One clause #

The honest residual’s floor is visible from the residual itself. Each check either halves it, which is what a converging conjugate-gradient run does over five steps on these grids, or it does not; and when two checks in a row do not, the run has reached the accuracy its arithmetic allows. The stagnation rule stops there.

It stops every one of the thirty runs within forty steps — at 15 to 30 steps, for 18 to 36 products. Below 53 bits its answer is the recurrence rule’s answer to within one per cent on every run, because by the time either stops the error has long since stopped improving. In double it is more accurate than the recurrence rule, because waiting for the double residual to pass the tolerance overshoots by up to a check: on the 14 × 14 grid the error is $2.3\cdot 10^{-14}$ against $2.8\cdot 10^{-12}$, for 30 products against 22. Over the thirty runs it spends 720 products against the recurrence’s 605, and against the 438 an oracle that knew the answer would have spent.

And at the precisions where the floor is high it is cheaper than the recurrence’s test. At 8 and 11 bits on the grids from 8 × 8 up the floor arrives by the tenth step, the second stagnant check comes at step 15, and the run stops with 18 products; the recurrence’s own residual, which cannot see the floor, takes 19 to 30 steps to reach $10^{-12}$. On the 6 × 6 grid the two are within two products of each other.

What it reports #

The part of the earlier essay that does survive is the report. At the stagnation rule’s stop the double residual is within a factor of a quarter to five of the error on all thirty runs — $2.2\cdot 10^{-5}$ error and $8.9\cdot 10^{-5}$ reported on the 10 × 10 grid at 16 bits; $6.0\cdot 10^{-3}$ and $2.0\cdot 10^{-2}$ at 8 bits. The recurrence rule on the same runs reports $9.8\cdot 10^{-13}$ and $2.5\cdot 10^{-13}$. Turn the dial: on every grid the recurrence’s line is flat at the tolerance and the double residual’s follows the error down the precisions.

Divided out, the difference is ten orders of magnitude. The recurrence rule’s reported number over its error runs down to about $4\cdot 10^{-11}$ — on the 10 × 10 grid at 8 bits it reports a residual twenty-four billion times smaller than the error. The stagnation rule’s ratio stays between 0.35 and 5 on every run, which is what the residual-to-error relation on a matrix with condition number 19 to 91 permits. A caller who reads it learns, to within a factor of five, how wrong the answer is, and learns it from a number the solver already computed.

Where a run waiting for the honest test ends #

The ends of the waiting runs have their own pattern, and it is a warning about a failure mode a code would rarely see. At 53 bits the runs could stop at 15 to 25 steps and did, but continued past that they would end at 122 to 233 steps, when the recurrence residual underflows; with less precision the breakdown comes later, because a coarser arithmetic shrinks the recurrence residual more slowly once its steps are dominated by rounding, and on the two largest grids at 16 bits and below the cap arrives first. A code that waited for a test its arithmetic cannot pass would therefore stop at a point determined by the format’s underflow behaviour or by an iteration limit somebody typed — on these problems, ten to twenty times later than the answer stopped improving, with the same answer.

The rule as a target #

The stagnation rule turns the stopping test from a promise the caller made into a measurement the run makes. A target the residual can promise went the other way in inexact Newton: it set the residual tolerance from a forward-error target and a condition-number estimate, and found the one target in twenty that a residual could not certify because it asked for a residual below rounding. The two meet here. At 16 bits on these grids a tolerance of $10^{-12}$ is not certifiable — the double residual’s floor is seven orders above it — and the stagnation rule discovers that at step 15 and reports what can be certified instead, $8.9\cdot 10^{-5}$. A code that combined the two would set its tolerance from what the caller wants and stop at the larger of that tolerance and the floor it observes, reporting which one it stopped on.

The tolerance that buys no agreement found the reverse face of the same coin: asking for four more orders of accuracy bought them, and bought no agreement between runs. Below the floor, asking buys nothing at all, and a rule that knows when it has reached the floor is the only one that stops asking.

What follows for a mixed-precision solver #

The part of a solver that may be rounded drew the line that made this sweep possible: a quantity that steers may be rounded and a quantity that measures may not. This essay adds the corollary for the stopping test, which is a measurement that also steers. It must be computed in the wide format, or it measures nothing; and it must accept the wide-format answer’s floor, or it never steers anything at all. The stagnation clause is the acceptance. It is what buying the accuracy back builds into iterative refinement as a matter of course — refinement stops when the correction stops shrinking, not when the residual reaches a number chosen in advance — and its absence from a single Krylov solve run in reduced precision is the gap.

The number that is re-derived priced residual replacement for a Krylov method in double: recompute the residual from A and b periodically and assign it back to the recurrence. In reduced working precision that would make the recurrence’s residual honest too — and it would then stagnate at the same floor, and a test on it would wait in the same way. Replacement fixes what the number means; only a rule about stagnation fixes when the run stops. And a stopping test is a race found the recurrence’s test producing eleven iteration counts from thirteen partitionings of one solve, each crossing the tolerance on a slightly different step; a stagnation test crosses no fixed line, and its decision is made on a ratio of two honest residuals five steps apart, which is the kind of quantity that does not care which partition summed it.

What these runs do not show #

One operator family, one preconditioner applied exactly, one right-hand side, a check every five steps and a halving criterion chosen rather than tuned. A check interval of five is short enough here because these grids converge by about a decade every five steps; on a harder problem converging more slowly, a halving test over five steps would call a slow phase stagnation, and the interval would have to scale with the observed rate. And the cost of a check is one product with A in double, which on hardware where the reduced format is the whole point may cost much more than a reduced-precision step.

Still open: an interval that reads the rate, and the floor in advance #

A check interval set by the rate. The stagnation clause’s interval of five steps works because one decade comes every five steps here. A rule that set the interval from the last two checks’ observed reduction — long while progress is slow, short while it is fast — would make the clause safe on slowly converging problems. The prediction with a sign is that on the unpreconditioned Laplacian, which converges several times more slowly, the fixed five-step interval stops some runs early at above twice the attainable error, and the rate-set interval does not.

The floor before the run. The floor the double residual stops at scales with the working precision’s unit roundoff and with the grid. If it is predictable from those two numbers to within a factor of a few — the earlier essays found the error tracking u to a factor of 1.5 — then a code could set its tolerance to the floor before it starts, and the recurrence’s own cheap test would then stop in the right place. Whether the prediction holds across grids is the measurement that would make the double check unnecessary rather than merely sufficient.