A run that is over at step five

A solver is watched while it runs. The residual falls, the fall is compared against a tolerance, and the comparison decides when to stop — an arrangement so ordinary that the two things it assumes are never stated. It assumes the residual is still moving, and it assumes that moving further is what another iteration buys.

On a conjugate gradient whose every iterate is cut back to a rank budget, neither assumption holds, and the arithmetic that breaks them is the rank growth that forces the truncation in the first place. That essay establishes what a budget is worth: the floor the residual settles at is a property of the answer rather than of the truncation, so the same budget is free on a problem whose solution is a train and useless on one whose solution is not. It is a statement about the budget, and it holds the run length fixed at seventy steps.

This one moves the axis the other holds still. Same operator, same method, same two right-hand sides, same seven budgets — and the run taken to thirty steps, to forty, to fifty, to ninety and to a hundred and twenty. Three numbers come out of it. The floor barely moves for four times the work. The step at which the run reaches that floor is early, and at the tightest budget it is step five. And past the point where the budget stops binding at all, the extra steps do not merely fail to help: they run backwards, by a factor of twenty-four.

That is the picture of a truncation doing nothing, and it is the setting the rest of this page needs. Seven is above the answer’s own rank, so no column is ever discarded; the budget is present in the code and absent from the result. Every claim below about steps beyond the floor is made in that regime, where the only thing left in the run is the arithmetic.

The measurement is on the trace, not on the last entry #

A ladder of floors reports one number per budget, from the end of the run. That number cannot say when the run got there, and when it got there is the whole question. So the measurement here is on the residual at every step of a hundred and twenty, at each budget, on both right-hand sides.

The statistic is the first step whose residual is within a tenth of the smallest residual the entire hundred and twenty steps ever attain. It is a deliberately generous test — it allows the run ten per cent more residual than it will ever have again, and asks how early it first gets there.

With a constant right-hand side, that step is 5 at a budget of one, 36 at two, 42 at three and 59 at four. At the tightest budget the residual is 1.273·10⁻¹ at step five and 1.174·10⁻¹ at step a hundred and twenty: a hundred and fifteen further iterations, each of them a full application of the operator followed by a recompression, purchase a nine per cent reduction. On the same run the residual is inside a factor of two of its final value at step 4.

The pattern across the budgets is worth reading, because it is the opposite of the one a reader of convergence curves expects. A tighter budget does not make the run slower; it makes it shorter. One column ends the run at step five, four columns keep it alive to step fifty-nine, and the reason is that the floor a tight budget imposes is high enough that the iteration hits it almost at once. The budget is not a speed setting. It is a place the run stops.

Four times the work moves the floor by less than two #

The five ladders differ by the length of the run and by nothing else. Their structured arms:

Read down each column. Quadrupling the iteration count from thirty to a hundred and twenty improves the floor by a factor of 1.015 at a budget of one, 1.124 at two, 1.184 at three and 1.846 at four. The largest of those is under two, and it is the only one a plot would show at all.

Read across each row instead and the picture is the one the ladder was drawn for: about two decades per column, at every run length. The floor is set by the budget to within a per cent or two, and by the run length hardly at all. Whatever the iteration is doing after its first few dozen steps, it is not converging.

The rank-four column is the interesting one and the reason is arithmetic rather than luck. Four is one short of the answer’s own rank, so it is the last budget at which the truncation removes anything at all, and therefore the last at which the residual has any structure left to recover. Everything to its left is so tightly constrained that the iteration is finished within a few steps; everything to its right is unconstrained and finished for a different reason. A run that improves visibly with length exists only in a single column of this ladder, and that column is one wide.

There is a second reading of the same table, and it is the one worth having before provisioning anything. The gap between a thirty-step run and a hundred-and-twenty-step run, at every budget on this problem, is smaller than the gap between two adjacent budgets, which is a factor of about a hundred. Iterations and columns are the two things a caller can spend, and one of them is worth two orders of magnitude and the other is worth eight per cent. That is not the trade the rate a condition number predicts describes, because that rate is about an iteration free to go wherever the Krylov subspace allows, and this one is not.

Past the answer’s own rank the extra steps run backwards #

At a budget of five, six or eight the three residual traces are identical, entry for entry. That is the over-budgeting result arriving in the trace rather than in a summary: once the allowance exceeds the answer’s rank, raising it further changes not one number in the run.

What those identical runs do is the finding. The residual reaches its minimum of 1.552·10⁻¹⁴ at step 39. It is above twice that minimum by step 46, above ten times it by step 74, and reads 3.767·10⁻¹³ at step 120 — a factor of 24.3 in the wrong direction. Over all eighty-one steps after the minimum it never once falls: the rise is monotone, with no exceptions.

It is also close to a straight line rather than a random walk. A least-squares fit over steps fifty to a hundred and twenty gives 4.73·10⁻¹⁵ of relative residual added per step, and no point in that range departs from the fitted line by more than 5.3%. A drift that accumulated by cancellation would grow like the square root of the step count; this one grows like the step count, which says that each step adds roughly the same amount and that the additions do not cancel.

The obvious suspect is the method. Conjugate gradients in finite precision lose the orthogonality their short recurrence rests on, which is what the essay on an orthogonalisation nobody calls one measures, and a residual that climbs late in a long run is a familiar symptom of it. The suspect is wrong here, and one control settles it.

Run the same method on the same operator and the same right-hand side with the truncation removed entirely — no budget and no tolerance, the iterate carried in full. It reaches 1.258·10⁻¹⁵ at step 35 and then reads 1.258·10⁻¹⁵ at step 40, at step 70 and at step 120. Not approximately: the same number, to every digit, eighty-five steps later. The un-truncated run is flat and the budgeted one climbs by twenty-four, so the climb belongs to the only thing that differs between them, which is the round trip through the compressed format applied to every iterate.

That is worth stating precisely, because “the truncation removes nothing” and “the truncation does nothing” are different claims and only the first is true. At a budget of five the decomposition keeps every column it is offered — the cut ranks asked for are 1, 2, 3, 4, 5, 5, 5 and the ranks kept are 1, 2, 3, 4, 5, 5, 5 — so no rank is discarded. But a decomposition and a reassembly are not the identity map on a floating-point array. Each round trip re-rounds the iterate at the level of the format’s own tolerance, afresh at every step, and a hundred and twenty of them is a hundred and twenty small perturbations to a vector whose residual is already at the rounding level. The same recompression that costs nothing when the residual is 10⁻⁴ is the dominant term at 10⁻¹⁴.

So the honest description of a long run in this format has two halves that point in opposite directions. Where the budget binds, extra steps buy a few per cent. Where it does not bind, extra steps cost a factor that grows without limit, because the drift is linear and nothing in the run opposes it. Between the two there is no regime in which running longer is the right instruction, and that is not a statement about this operator’s conditioning — a stall that was blamed on the arithmetic and belonged elsewhere is the neighbouring case where a truncation inside a factorisation turns out to cost nothing measurable at all.

The unstructured right-hand side is over at step one #

The second arm of every ladder above is the same operator with independent normal entries in the right-hand side, whose answer has no low-rank structure to find — the solver’s encounter with a kernel with nothing to compress.

Applying the same trace statistic to it gives an answer that barely needs a figure. The residual is within a tenth of its hundred-and-twenty-step best at step 1 for budgets of one, two, three and four, and at step 2 for a budget of eight. At thirty steps the ladder reads 0.969, 0.925, 0.872, 0.800 and 0.469; at a hundred and twenty it reads 0.969, 0.925, 0.874, 0.802 and 0.470. Ninety additional iterations change the third significant figure of two entries out of five, upward.

A run that is over at its first step is not converging slowly. It is not converging, and the only signal distinguishing it from a run that will eventually succeed is the value it is stuck at, which is a number near one rather than a number near zero. That distinction is available from the first iteration and is thrown away by any stopping rule that waits for a tolerance.

No tolerance fires #

The rule this collection normally recommends is to iterate until the relative residual is below a tolerance. Applied to these runs it produces the following, where each entry is the first step at which the residual goes below the tolerance in a hundred and twenty:

Twelve of the twenty entries are “never”, and the failure is not graceful. A tolerance of 10⁻⁶ at a budget of four misses by a factor of five and the run continues for however many steps the iteration limit allows, producing nothing after the fifty-ninth. A tolerance of 10⁻² at a budget of two misses by a factor of five as well, and there the run was over at step thirty-six. In both cases the tolerance is nearly satisfied, which is the worst case for a rule whose only outputs are “stop” and “continue”.

And the entries that are not “never” are equally unhelpful in the other direction. At a budget of five, a tolerance of 10⁻⁸ stops the run at step 23 with a residual six orders above the 1.55·10⁻¹⁴ the same run reaches sixteen steps later. The tolerance decided the answer, the budget was capable of much more, and nothing in the output says so. This is the same structural complaint as a stopping test that is a race, where one matrix, one right-hand side and one tolerance produce eleven different iteration counts — there the rule fires at a step that depends on something other than the mathematics, and here it fires at a step that has nothing to do with what the run was capable of.

A rule that fires, and what it costs #

The rule that works on these runs asks about the change in the residual rather than its value: compare the residual against its own value ten steps earlier and stop when it has not fallen by at least a tenth.

Measured on the constant right-hand side, it fires at step 15 at a budget of one, 28 at two, 36 at three, 49 at four and 44 at five — saving 105, 92, 84, 71 and 76 of the hundred and twenty steps. What it pays for that is the excess over the best residual the full run ever attains: 1.036, 1.136, 1.129 and 1.147 at budgets one to four. Under fifteen per cent of the residual, for between three-fifths and seven-eighths of the work.

At a budget of five it stops at 1.671 times the best-ever residual, and that number reads worse than it is. The minimum there is at step 39 and the rule fires at 44, so it is late rather than early — and being late is the direction that matters, since the run it declined to continue would have reached 24 times the minimum by step 120. On the unstructured right-hand side the same rule fires at step 11 in every case, at 1.002 to 1.003 times the best-ever residual, which is a solver that correctly gives up on the ninth wasted iteration rather than the hundred and nineteenth.

Two qualifications belong with that recommendation and neither is small. The rule needs a residual at every step, and the residual used throughout here is recomputed as b − Ax from the current iterate rather than updated by the recurrence — an extra application of the operator each step, and the reason it is worth paying is the gap between the residual a method reports and the one its answer has. The same gap is measured for a different method in the number that is re-derived, where a recomputed residual stays honest while the basis it came from does not. A stagnation rule fed the recurrence’s own residual would be reading a number that has stopped describing the iterate, and would stop at the wrong step for a reason that has nothing to do with the budget.

The second qualification is that a threshold on the ten-step ratio is itself a constant somebody types, with the two-sided failure that deciding a zero has arrived is about: set it loose and the run stops while the residual is still falling, set it tight and the run continues into the drift. The measurements above use a tenth over ten steps; a ninety-nine-hundredths threshold over the same window moves the stopping step from 49 to 107 at a budget of four and buys a further three per cent of residual, which is the trade in its entirety.

Where this stops being true #

The step counts are specific to this problem and should not be carried anywhere unexamined. The operator is the three-dimensional model problem at ten points a side, a Kronecker sum whose condition number is 48.37; a finer grid raises that and lengthens every run, and the point at which a budget starts to bind moves with it. What is claimed to transfer is the shape — an early floor, a flat middle, and a drift at the end — and not the number five.

The measurement also relies on an arrangement no production solver has. The iterate is carried as a full array so that its true cut ranks can be read at every step, which is what the compressed format’s storage is made of and precisely what a code in that format has thrown away by the time anyone could ask. A real solver sees the residual and the storage and not the rank the step wanted.

And “over” here means the residual has stopped moving, which is not the same as the answer being right. The value the run stalls at is a residual, and a small residual is not a small error: 5.07·10⁻⁶ at a budget of four is a statement about how well the iterate satisfies the equations, not about how close it is to the solution, and the two are separated by the condition number. The floor is a bound on what iterating can achieve, not a certificate of what has been achieved.

What follows for a code in this format #

Provision columns, not iterations. A budget is worth about two decades and a quadrupling of the iteration count is worth eight per cent. A caller with a fixed compute budget and any freedom over memory should spend it on the second, and this is the reverse of the usual advice for an iterative method.

Cap the iteration count near the floor and do not fear capping it early. The stagnation rule above stops between step 15 and step 49 on these problems at under fifteen per cent excess residual. A limit set generously is not the safe choice it appears to be, because past the answer’s rank the extra steps make the answer worse.

Measure the right-hand side before solving. The unstructured arm is over at step one, and the ranks of b are available for the cost of a few decompositions of its reshapes. The budget axis arrives at the same check from the other direction.

Do not compare a truncated run against a convergence rate. The rate a Krylov method is entitled to assumes iterates that stay in the Krylov subspace, and a projection onto a low-rank set at every step removes them from it — the same geometry that sends an iteration walking out of its own set somewhere its limit is not. A run that stalls at 10⁻⁴ has not failed to converge; it has converged to the thing it was constrained to reach.

And an adaptive tolerance is the better instrument than a fixed budget, for the reason a tolerance that reads its own residual gives about inner solves: a truncation level tied to the current residual keeps the representation error below the iteration error at every step, so the run neither stalls above what it could reach nor drifts once it gets there. A fixed rank budget can do neither, because it cannot know which regime it is in.

The refusal #

The claim under test is the one a rank budget invites once over-budgeting has been shown to be free: that the budget is a pure memory setting, so raising it can only help and it should be set as high as the machine allows.

The budgeted solver is fed a request for a rank of forty on a problem with ten points a side, and the assertion that a budget is a free parameter has to reject it. No cut of a 10×10×10 array can have rank above ten, so forty names a rank that does not exist, and the refusal is about the object rather than about the machine.

The measurements on this page tighten that ceiling considerably. The mathematical bound is ten; the answer’s own rank is five; and the traces above show that every column above the fifth is inert and every step past the thirty-ninth is harmful. A budget set as high as the machine allows would buy exactly what a budget of five buys, entry for entry, while the run drifted upward at 4.73·10⁻¹⁵ a step. The counterweight to a knob that cannot be set too high is a run that cannot be made too long, and both directions are measured on the same object — the arrangement four knobs and one floor makes on a problem whose answer is known, where parameters are compared against one another rather than each defended alone.