A bound on the fall, not the error

A short window from the start ended a run of essays on how to stop conjugate gradients in reduced precision. The clause that won is Hestenes and Stiefel’s: the sum $\sum_{j=k}^{k+d-1}\alpha_j\|r_j\|^2$ over a window of $d$ steps is a lower bound on the squared energy error at step $k$, so stopping when its square root falls below $u\,\|x_k\|_A$ stops when the error itself has come down to the working precision — $d$ steps late, since the window looks ahead. On forty runs, Laplacians on five grids at four precisions, a fixed window of five stopped every run within 1.097 of its least error and beat every rule that started long and shrank.

Those forty runs were steady: the error fell, more or less geometrically, until rounding stopped it. The essay asked what happens when it does not. “Build the operator with a cluster of eigenvalues that conjugate gradients must resolve before its next decade. The prediction with a sign is that window 5’s bound falls below the threshold on the plateau on no run — because the plateau’s error sits far above $u\|x\|_A$, and the bound, a lower bound on that error, sits at most a little below it — so that the short window’s safety holds through a stall as well, and the case for any longer window disappears.”

The reasoning has a gap in it, and two kinds of stall find it from opposite sides.

Two ways to stall #

The first kind of stall is rounding’s. Strakoš’s matrices are diagonal, with eigenvalues $\lambda_i = \lambda_1 + \frac{i-1}{n-1}(\lambda_n - \lambda_1)\rho^{\,n-i}$ crowded towards the bottom of $[0.1, 100]$; in exact arithmetic conjugate gradients converges on them steadily, and in floating point it stalls, repeatedly, while the Lanczos process underneath it loses orthogonality and builds a second copy of an eigenvalue it has already found. An eigenvalue that arrives twice is the account of those copies. Order 48, five values of $\rho$ from 0.6 to 0.95, each at 24, 16, 11 and 8 bits: twenty runs, and the larger $\rho$, the more of the run is stalled. More bits do not cure it: in double precision the run at $\rho = 0.95$ still stalls on seventeen steps, because what stalls it is the loss of orthogonality, and that sets in as soon as the first eigenvalue converges at any precision. Keeping the vectors, and losing the bound met the same mechanism in an eigenvalue code, where a bound computed from the recurrence kept falling long after the quantity it bounded had stopped.

The second kind is exact arithmetic’s. Forty-seven eigenvalues spread evenly over $[1, 100]$ and one more far below them, at $10^{-2}$, $10^{-3}$ or $10^{-4}$, with the right-hand side weighted so that the low eigenvalue’s component carries a share of $\|x\|_A^2$ of $10^{-2}$ or $10^{-4}$. Conjugate gradients reduces the forty-seven first, because that is where nearly all the energy is, and the error then sits at the square root of the low component’s share — a tenth or a hundredth — until the method spends a degree of its polynomial on a root near the low eigenvalue. Twenty-four runs, three depths by two shares by four precisions. This is the stall the prediction described: an eigenvalue the method has to resolve before the error can fall again.

On the twenty Strakoš runs window 5 behaves exactly as the prediction said: the worst stop is 1.115 times the least, at $\rho = 0.95$ and 16 bits, and the rest are within 1.07. On the twenty-four isolated runs it stops more than 1.5 times above the least on six, and on three of those at 8.2, 8.7 and 9.7 times. Every one of the six is at 8 or 11 bits — four at 8, two at 11, none at 16 or 24 — and in double precision the same twenty-four operators give one stop above 1.05, at 1.23. The prediction holds on the stall it pictured least clearly and fails on the one it described.

What the window sum measures #

The window sum is not, at bottom, an estimate of the error. In exact arithmetic it is the error’s loss: $\sum_{j=k}^{k+d-1}\alpha_j\|r_j\|^2 = \|e_k\|_A^2 - \|e_{k+d}\|_A^2$, the energy the error gave up over the window. It is a lower bound on $\|e_k\|_A^2$ only because $\|e_{k+d}\|_A^2$, the part not given up, cannot be negative. When the error falls steadily the part given up over five steps is most of it and the bound is tight. When the error waits, the part given up is small, and the bound is small, however large the error is.

The run the dial opens on has its low eigenvalue at $10^{-4}$ carrying $10^{-2}$ of the energy, at 8 bits. The error falls to 0.1 in twenty steps and stays there until step 55. Over those steps the forty-seven are still losing what they have left, geometrically, and the window sum, which sees only their loss, falls with them: by step 22 it is under $2 \cdot 10^{-3}$, below the threshold of $4 \cdot 10^{-3}$, and window 5 stops at step 27 with the error at 0.10. The run goes on to 0.012 at step 100. The residual does not help in the middle of the stall either. On the same run its norm is $6 \cdot 10^{-2}$ at step 20 and $8 \cdot 10^{-3}$ at step 30, falling with the forty-seven while the error waits; then it climbs, to $1.5 \cdot 10^{-2}$ at step 40 and $0.16$ at step 50, twenty times above where it was, as the method starts to spend its polynomial on the low eigenvalue. The residual weights each component by its eigenvalue squared, so it reports the forty-seven almost exclusively until the polynomial disturbs them to reach the low one. It signals the end of the stall, by rising, and says nothing at the start. Turn the dial to the Strakoš run and the error stalls in the same visual way, but the bound stalls with it: a rounding stall is a repetition — the method is re-finding a direction it has already used — and the error does still fall over five steps, by enough that the window sum stays within a factor of two of it.

On the 217 stalled steps of the Strakoš runs the bound is 0.55 to 0.86 of the error. That is the prediction’s “at most a little below”, and it holds there without exception. On the isolated runs it is 0.12 at the least with the low eigenvalue at $10^{-2}$, 0.040 at $10^{-3}$ and 0.013 at $10^{-4}$, with medians of 0.39, 0.18 and 0.08. The deeper the isolated eigenvalue, the longer the stall and the further the bound falls below the error before it ends.

The depth sets the blindness #

How far the bound falls has a number attached, and it is the square root of the isolated eigenvalue.

At every depth, both shares and both precisions, the least ratio is 1.2 to 1.3 times $\sqrt{\lambda_{\text{low}}}$. A rough argument gives the shape, though not the constant, and is a guess rather than a derivation. Near the end of the stall the forty-seven have been reduced until the polynomial can afford a root near the low eigenvalue, which happens when what is left of their energy is comparable to the low component’s energy times the factor the root costs them — and the window sum, which is their loss, sits about that factor below the error. The factor is the ratio of the low eigenvalue to the spread above it, and a square root comes from comparing energies rather than errors. The stall lengthens with the depth as well: the eight isolated runs at each depth spend a median of 9, 13 and 19 steps stalled with the low eigenvalue at $10^{-2}$, $10^{-3}$ and $10^{-4}$, and the longest, at $10^{-4}$ and 8 bits, 36. A deeper eigenvalue costs the polynomial more to resolve, so the method waits longer before resolving it, and the bound has longer to fall.

One run at 24 bits shows the edge of the effect. With the low eigenvalue at $10^{-4}$ carrying $10^{-2}$ of the energy, window 5 stops at step 60 with the error 1.48 times the least, which comes at step 75: not fooled by the stall, which had ended, but caught on the steep descent after it, where the error is falling fast and the window has five steps of fall to report. That run is the reason the count of fooled runs uses 1.5 as its line; at 1.1 there are twelve runs over it, none of them at 16 bits.

Whatever the constant, the dependence is the reason precision matters: the bound reaches down to about $\sqrt{\lambda_{\text{low}}}$ times the plateau’s height, and the threshold is $u$. At 24 and 16 bits $u$ is below that on every run; at 11 and 8 bits it is not on the deep ones, and those are the runs that stopped.

A floor the error has not reached found the other side of the threshold’s arithmetic: a clause that stops when a quantity reaches the precision’s floor is only as good as the quantity’s relation to the error. There it was the residual, which can reach the floor while the error has not. Here it is the bound, which can reach it while the error is a hundred times above it — and the same essay’s caution, that a lower bound is worth exactly as much as the reason it is low, is the whole of the failure.

Longer windows, and how long #

The essay this one tests concluded that the case for any longer window had disappeared. A stall restores it, and the figure says by how much.

Window 10 is fooled on five runs, with the same worst of 9.7. Window 20 is fooled on two, at 1.54 and 1.57, and stops within 1.43 elsewhere. Window 40 is within 1.11 of the least on every run. A window is safe through a stall when it is longer than the stall: the sum then includes the steps after the method resolves the low eigenvalue, when the error falls again and the loss is large. The stalls here last twenty to forty steps at low precision, which is why forty is the length that works and twenty is not quite.

Counted in steps, the price is large. Across the twenty Strakoš runs window 5 stops 47 steps past the least in all, window 20 344 and window 40 745; across the twenty-four isolated runs, 34, 297 and 792. Window 40 buys the isolated family its safety with about thirty-two extra steps a run, at every precision, including the twelve runs at 16 and 24 bits that window 5 had stopped safely.

That is a price the Strakoš runs do not ask. On them, window 40 stops about 35 steps after window 5 with no gain in safety at all — the worst stop goes from 1.115 to 1.065 — and on the forty steady runs of the earlier essays the extra delay cost overrun with nothing to show. The choice of window is a bet on which kind of stall the operator has, and the clause cannot tell them apart from inside the run: both look like an error that has stopped falling, and only one of them has a bound that stops falling too.

What was mistaken #

The prediction’s argument had two steps. The plateau’s error sits far above the threshold: true on every run, by a factor of 2.6 at the least — a hundredth against 8-bit precision — and of more than a million at the most. The bound sits at most a little below the error: true on rounding’s stalls and false on exact arithmetic’s, by up to a factor of eighty. The first step was a fact about the error and the second a belief about the bound, and the measurement says the belief was calibrated on the only stalls the earlier runs had seen. Five steps is a rate made the same kind of calibration explicit when it set a stagnation interval from an observed rate; an interval learned on steady runs inherits their steadiness.

The residual was never a candidate here. The reading that never moves and the honest residual is not a stopping test found the computed residual in reduced precision pinned near a floor while the error moved by eleven orders, and recomputing it in double made a good report and a poor test. A later look is a worse stop is where the window sum replaced it, precisely because it reads the error’s loss directly. That directness is the strength the steady runs rewarded, and on an exact stall it is the whole weakness: a loss is not a level.

A stopping test is a race framed every stopping clause as a race between a computable quantity and the error it stands for. A stall in exact arithmetic is the case where the two runners part company on purpose: the method is doing useful work the error cannot yet show, reducing components that are already small so that it can afford the root it needs, and the window sum, which reports useful work, reports it faithfully. It is the reading of that report as an error that fails.

The share decides which runs fall in, and in a direction the prediction’s first step would not suggest. Five of the six fooled runs have the low eigenvalue carrying $10^{-4}$ of the energy, a plateau at a hundredth; one carries $10^{-2}$, a plateau at a tenth. The higher plateau is further above the threshold, but that is not what protects it. What protects a run is the bound’s height, the plateau times about $\sqrt{\lambda_{\text{low}}}$, and the bound on a low plateau starts nearer the threshold before it has fallen at all. A small leftover component is the dangerous one: large enough to hold the error a hundred times above the precision, small enough that the method’s attention to it shows in the window sum only at the end.

What forty-four runs do not show #

Both families are diagonal, so the operator’s eigenvectors are the coordinate axes and the right-hand side’s weights are chosen rather than found. A preconditioned operator with a few eigenvalues that the preconditioner missed is the realistic case of the isolated family, and there the low component’s share is whatever the problem gives it. The shares here, $10^{-2}$ and $10^{-4}$, put the plateau at a tenth or a hundredth, well above 8-bit precision; a plateau below $u$ would be invisible to every clause, and correctly so. And the stalled-step test — ten steps lowering the error by less than half — is a definition chosen to catch both kinds; a stricter one would count fewer steps and leave the ratios’ extremes unchanged.

Still open: a window that knows its own stall, and a preconditioner’s leftover #

A window that grows when the error does not. The bound cannot see a stall in exact arithmetic, but the residual can: the forty-seven’s remainder shows up in $\|r_k\|$, which falls geometrically while the error waits, at the same rate as the window sum. The prediction with a sign is that a clause which doubles its window whenever the ratio of the window sum to $\|r_k\|^2\alpha_k$ — a single step’s share of the window — stays constant for five steps, and halves it otherwise, stops all twenty-four isolated runs within 1.2 of the least, and the twenty Strakoš runs within two steps of window 5.

A leftover eigenvalue. Incomplete Cholesky on a Laplacian with one weakly coupled patch leaves the preconditioned operator with a handful of small eigenvalues the preconditioner did not catch. The prediction is that at 11 bits window 5 stops such a run more than twice above its least error on the grids where the smallest preconditioned eigenvalue is under $10^{-3}$, and that window 40 does not — the first operator built by an algorithm rather than by hand on which the window’s length decides safety.