A floor the error has not reached

Five steps is a rate found a stagnation clause that stops every reduced-precision conjugate-gradient run on three problems within two fifths of the least error the run reaches. It recomputes the residual in double, checks it at intervals set from the reduction it last saw, and stops when two checks in a row fail to halve it. Its price is the overrun: once a run is on its floor the clause’s last interval is long, and on the preconditioned Laplacian it ran 1,661 steps past the least error, summed over twenty runs, where a clause checking every five steps ran 198.

The essay located the fix in a number the run does not have. “A run on its floor has reached the error its precision allows, and the reading that never moves found that floor scaling with the working precision’s unit roundoff and the problem. If it were predictable from those two numbers, a clause could stop as soon as the double residual came within a small factor of it.” The prediction it signed was specific: the floor is predictable from the unit roundoff and the grid to within a factor of four on all three problems, and a clause stopping within that factor of it keeps the rate-set clause’s safety and runs no further past the least error than the fixed one.

Both halves fail, and the second fails for a reason the first sentence of that quotation already contained.

Sixty runs, and what their floors are #

The runs are the earlier essay’s. The Laplacian on grids of 6, 8, 10, 12 and 14 points a side, at 24, 16, 11 and 8 bits of working precision, solved with an incomplete-Cholesky preconditioner, without one, and without one after scaling its rows and columns by a seeded diagonal spanning a decade and a half. Each run goes to a step cap with the residual recomputed in double, $\|b - Ax_k\|/\|b\|$, and the energy-norm error recorded at every step. The floor is the least double residual the run reaches. The reference solution is exact to double precision, so every error is measured rather than estimated.

The residual cannot fall below a floor for a reason that needs no theory of conjugate gradients. The iterate $x_k$ is stored at the working precision, so each of its entries carries a relative rounding error of about $u = 2^{-\text{bits}}$. Computing $Ax_k$ in double from those rounded entries reproduces the error exactly: the residual of a vector rounded to $u$ is about $u$ times the size of the products that make up $Ax$, and it cannot be smaller whatever the method did. The size of those products, entry by entry, is $|A||x|$. So the natural prediction is $u\,\| |A||x| \|/\|b\|$, the same quantity a condition number scaling cannot move builds its componentwise measure from.

It works. Across all sixty runs the floor over $u\,\||A||x|\|/\|b\|$ lies between 0.60 and 6.39, which is a factor of 3.26 either side of 1.96. Inside each problem the band is narrower: 0.60 to 1.17 with the preconditioner, 0.77 to 1.66 without, 1.22 to 6.39 on the scaled problem, where the floor sits highest above the prediction. Seven decades of floor, from $10^{-7}$ at 24 bits to $10^{-2}$ at 8, follow the prediction’s line within that band.

The grid makes the prediction worse #

That is within the factor of four the earlier essay asked for, but not from the two numbers it named. The quantity $\||A||x|\|/\|b\|$ reads the solution, and the prediction was meant to come from the unit roundoff and the grid. So the next measurement asks what the grid adds.

The unit roundoff alone needs a factor of 4.25 either side: the floor over $u$ runs from 1.27 to 22.95. Multiplying by the number of unknowns, the simplest way to put the grid in, makes it 6.73. Multiplying by $\kappa(A)$, which grows with the grid like its square, makes it 23.92. Only the two predictors that read the solution come inside four: $u\,\|A\|\|x\|/\|b\|$ at 3.98 and the componentwise one at 3.26. The grid does not help because the floor does not follow it.

At 16 bits the preconditioned run’s floor over $u$ is 2.3, 7.7, 5.8, 2.5 and 1.5 on the five grids in order: up by a factor of three and a third, then down by five. The unpreconditioned and scaled runs rise and fall in the same places. The dashed line is $\||A||x|\|/\|b\|$, at 2.13, 8.21, 7.61, 2.11 and 1.75, and it rises and falls with them. The grid’s effect on the floor is real and enters entirely through the solution: the right-hand side here is $b_i = \sin(1 + 0.7i)$, and how large a solution it produces relative to itself depends on how that sequence lines up with the grid’s low modes, which is not monotone in the grid’s size. A formula in $n$ or $\kappa$ has nothing in it that rises at 8 and falls at 12. The earlier essay’s phrase “scales with the working precision’s unit roundoff and with the grid” was half right: the precision enters as $u$ and the grid enters as whatever the solution’s products happen to be on it.

This does not stop the floor being known before the run in practice. $\||A||x_k|\|$ costs one product with $|A|$, and at any step the current iterate gives it to within the iterate’s error, which when the residual reaches its floor is at most a quarter of a per cent at 16 bits, 5 per cent at 11 and 31 per cent at 8 — and at 8 bits the prediction’s own band of 3.3 is the larger uncertainty. So the floor is available during the run, at the price of one extra product per check, and the measurements below use it that way.

The residual reaches its floor before the error reaches its least #

With the floor in hand, the clause the earlier essay proposed is simple: stop at the first check where the double residual is within four times the predicted floor. It is unsafe, and the figure at the top of the page says why. It takes each run at the step where the double residual first comes within four times the run’s own floor — not the predicted one, the floor the run actually reaches, so no error in the prediction is involved — and reads the error there against the least the run ever reaches.

The error is not at its least. With the preconditioner it is 2.21 to 9.03 times the least, median 4.88; without one, 1.04 to 6.84, median 4.56; on the scaled problem 3.70 to 26.1, median 12.6. The least error comes later: a median 2 steps later with the preconditioner, 8 without, and 76 on the scaled problem, where the longest wait is 153 steps. So “a run on its floor has reached the error its precision allows” is false in the precise sense that matters. The residual is on its floor long before the error is, because the residual is bounded below by the rounding of $x_k$ while the error goes on falling as the iteration keeps reducing the components of the error the residual weighs least. The reading that never moves and a small residual is not a small error are this site’s long record of the residual failing to report the error; this is the same failure in time rather than in size.

On the scaled 10 by 10 run at 16 bits the predicted floor is $1.17 \cdot 10^{-4}$ and the run’s own is $2.94 \cdot 10^{-4}$, 2.5 times above. The residual comes within four times its floor at step 138, with the error 8.2 times its least, and the least arrives at step 197. Between them the residual is nearly flat and the error falls by most of a decade. At 24 bits the residual reaches its floor at step 200 with the error 17 times its least and the least at 247; at 8 bits, at step 26 with the error 8.3 times its least and the least at 107. The floor moves with $u$, and the lag does not close.

How little the residual says between the two #

The gap is not a matter of the residual being noisy near its floor and hiding a trend. Between the step it first comes within four times its floor and the step of least error, the residual’s largest value over its smallest is a median 2.71 with the preconditioner and never more than 3.99, while over the same steps the error falls by a median factor of 4.88. Without a preconditioner the residual’s range is a median 3.30 against the error’s fall of 4.56. On the scaled problem the residual moves by a median 5.50, with one run reaching 12.8 as the residual rises again after its least, while the error falls by 12.6. In every case the residual’s movement over those steps is of the same size as the factor of four that defined the start of the window, so it carries no more information about the error than the threshold itself did.

The reason is the one conjugate gradients always has for a residual that lags the error. The residual is $A$ times the error, so a component of the error along an eigenvector with a small eigenvalue appears in the residual multiplied by that small eigenvalue. Once the rounding of $x_k$ sets a floor under the residual, the iteration can go on removing error along those directions and the residual has no room to show it. The scaled problem, whose condition number is the largest of the three, has the most of the error in such directions and waits longest. Buying the accuracy back made the complementary point for refinement: the residual computed in double is what lets a low-precision solve recover accuracy at all, and here it is also what sets the floor below which it can report nothing.

So a clause that stops near the floor is unsafe on every problem. Within four times the predicted floor it stops some run at 5.03 times its least error with the preconditioner, 3.46 without, and 5.01 on the scaled problem. Moving the threshold to twice the predicted floor brings those to 3.55, 2.99 and 1.56 — still over two fifths, and on the scaled problem only because the floor sits so far above the prediction that the residual rarely reaches twice it and the stall test ends most runs instead.

What the floor is for #

The floor cannot say when the error has stopped falling. It can say when the residual is about to stop, and that is what the rate-set clause’s overrun was made of: a long interval set while the residual was falling fast, landing many steps past the point where it flattened. So the floor’s job is to shorten the interval, not to end the run. The switching clause runs the rate-set schedule while the residual is more than four times the predicted floor and checks every five steps once it is within it, keeping the stall test unchanged: stop when two checks in a row fail to halve the residual.

On the two Laplacian problems it does what the earlier essay wanted. With the preconditioner its worst stop is 1.09 times the least error and its overrun 198 steps, exactly the fixed clause’s, against the rate-set clause’s 1,661. Without one, 1.10 and 123 steps, against the fixed clause’s 118 and the rate-set clause’s 1,372. It inherits the fixed clause’s speed where five steps are a fair test and the rate-set clause’s patience where the residual is still falling.

On the scaled problem it does not quite. Its worst stop is 2.20 times the least, against the rate-set clause’s 1.37, and its overrun 546 steps against 1,952. Five runs stop above one and a half times their least, every one of them before the least error rather than after it. This is the problem on which five steps do not halve the residual even while it is falling, which is why the fixed clause stopped all its runs by step 35 at up to 775,000 times their least. Near its floor the scaled run’s residual falls slowly enough that two five-step checks can fail to halve it while the error, 76 steps from its least in the median run, is still coming down.

The threshold trades one for the other. At twice the predicted floor the switching clause is as safe as the rate-set clause, worst 1.37, and saves almost nothing, 1,772 steps past against 1,952, because the scaled runs’ floors sit above twice the prediction and the switch rarely happens. At four times it is 2.20 and 546; at sixteen, 5.94 and 40; at sixty-four, 42.3 and 24. There is no threshold that is safe and cheap on the scaled problem, because what the clause would need to know there is not where the residual will stop but whether the error has, and the residual cannot say.

What a code can take from this #

The floor is the rounding of the iterate. $u\,\||A||x_k|\|/\|b\|$ predicts it within a factor of 3.3 either side of one constant on all sixty runs, at the cost of one product with $|A|$. A code reporting the double residual can report this beside it, and a reader seeing the two meet knows the residual has nothing further to say.

It is not a function of the grid. Formulas in the size or the condition number predict it worse than the unit roundoff alone, because the grid acts through the solution.

Reaching it is not converging. The error is a median 4.6 to 12.6 times its least when the residual gets there, and a clause that stops on it is unsafe on every problem measured. The honest residual is not a stopping test found that the double residual is the right thing to report and the wrong thing to stop on at the tolerance; it is also the wrong thing to stop on at its floor. A stopping test is a race found the bill for a run set by the moment a slowly falling residual crossed a line; near the floor the line is crossed slowly by construction, and the error is still moving when it is.

It is a good reason to look more often. Switching to five-step stall checks within four times the floor removes the rate-set clause’s overrun where five steps are a fair test and costs a factor of two on the problem where they are not. A tolerance that reads its own residual set an inner tolerance from the residuals it had seen and found the rule cheap and safe together; here the residual alone cannot be both, and the scaled problem is the case that shows it.

What sixty runs do not show #

Three problems on one family of grids, one right-hand side, four precisions and one preconditioner, all symmetric positive definite and all small enough for an exact reference. The floor’s prediction uses $|A||x|$ at the solution; a code would use the iterate, and the difference near the floor is the iterate’s error, from a fraction of a per cent at 16 bits to 31 per cent at 8, at the stops measured here, which moves no conclusion. The error is the energy norm, the one conjugate gradients minimises; a different norm would change how far it is from its least when the residual reaches its floor but not, on these runs, whether it is. The precision is simulated by rounding every vector operation to a number of bits, not by a hardware format with its own exponent range, and at 8 bits the floor sits at about $10^{-2}$, where the energy error’s least is not much below it.

Still open: what tells the error has stopped, and a stall in the middle #

An error estimate from the method. Conjugate gradients carries the quantities for a cheap lower bound on the energy error — the sum of $\alpha_j\|r_j\|^2$ over a window of the last $d$ steps. The prediction with a sign is that on the scaled problem a clause stopping when that estimate over a window of 20 steps falls below $u$ times the energy norm of $x_k$ stops all twenty runs within two fifths of their least error, and does so within thirty steps of the least on the median run, where the rate-set clause runs 1,952 steps past it in total.

A stall in the middle. The earlier essay’s second question stands unanswered and is sharper now. A plateau partway down a run’s residual is a stall the floor cannot be blamed for, and the floor prediction makes it distinguishable from the end. The prediction is that on a problem built with a cluster of eigenvalues that conjugate gradients must resolve before the next decade, the rate-set clause stops on the plateau above twice its least error on some run, and the switching clause does not, because the plateau sits above four times the predicted floor and the switch never happens there.