A walk needs a length

Conjugate gradients carries its residual forward rather than computing it, and the measurement of what that costs left this collection with a number and a shape. The number is nine and a half orders of magnitude between what a run prints and what its answer actually satisfies. The shape is an exponent: fitted over ten decades of iterate size, the gap grows with a slope of about a half, where the standard bound on it grows with a slope of one.

A half is what a sum with signs does. The bound has to assume every rounding points the same way; the roundings do not, so what accumulates is a walk rather than a total, and three unrelated recurrences measured together come out at 0.486, 0.554 and 0.507 against three bounds that are all linear.

A walk of k steps is √k long. That sentence is the whole of the explanation and it contains a free variable, because nothing in it says what k is. Two quantities in a conjugate gradient run are candidates. One is the number of iterations, which is the obvious reading of the word steps. The other is how far the iterates travelled, which is the quantity the fit was made against in the first place. They are different numbers, they are ordinarily confounded, and the whole account rests on which of them the square root is taken of.

The picture answers the question, in a sentence nobody had to test #

The figure above already carries an answer, printed under its slider, where the size of the matrix is the thing being turned. It reads:

A larger system takes more iterations, so there are more roundings to accumulate and more steps for the walk to take — and a walk of k steps is √k long however large k is.

That is the first reading, stated plainly and stated as though it followed. It does follow, from the premise that the walk’s steps are the iterations, and the premise had never been separated from the alternative because the two move together in every run anybody looks at. A harder problem takes more iterations and sends the iterates further, so a measurement across problems cannot say which term did the work.

The same note makes a second claim, one clause earlier, and it is the one that is easiest to check: that turning the size moves both series up together. There are two series on the figure. The upper one is the bound, u·‖A‖·max‖x‖, and it does move up with the size, because ‖A‖ is the largest eigenvalue and the construction puts that at n. The lower one is what the drift does. Whether it moves is the entire question, and it is answerable with the crank the figure already has.

The size is the control that separates them #

The matrix is diagonal with one eigenvalue at ε and the rest the integers from 1 to n, against a fixed right-hand side. Three things about that construction matter here, and the third is what makes the sweep an experiment rather than a survey.

The size sets the iteration count. More distinct eigenvalues spread over a wider interval means a longer run, and at ε = 10⁻⁴ the count goes 39, 51, 61, 70, 78, 86, 96 across n = 20, 30, 40, 50, 60, 70, 80. That is a factor of 2.46 in the number of roundings the recurrence commits, which is exactly the quantity the rate a condition number predicts is about.

The size does not set how far the iterates go. The largest iterate is not a property of the spectrum’s spread; it is set by the component of the solution along the tiny eigenvalue, which is the right-hand side’s first entry divided by ε. That entry is the same at every size. Measured, the largest iterate at ε = 10⁻⁴ is 9,308.66 at n = 20 and 9,308.66 at n = 80, and at every size between — identical to seven digits, at all seven.

And the two are ordinarily locked together by ε, which is why the question survived. Turning ε instead moves the largest iterate by ten decades and the iteration count by 1.44, from 39 steps to 56 at n = 20. The size turns the other knob and leaves the first alone. Between them the two controls separate quantities that no single sweep can.

The step count nearly triples and the gap does not move #

At the near end of every one of these sweeps the largest iterate is the same number. The step count is not, and the gap reads:

The prediction under test is arithmetic rather than a matter of judgement. If the walk’s length is the step count, going from 39 steps to 96 multiplies the gap by √(96/39) = 1.57. The ends of the column read 5.04·10⁻¹⁵ and 5.33·10⁻¹⁵, a factor of 1.06. The four values in between straddle both ends rather than climbing between them: the two smallest sizes bracket the two largest, and the whole column spans a factor of 1.40 with no order in it.

A scatter of 1.40 against a prediction of 1.57 is not a comfortable margin, so the same measurement was made over forty different right-hand sides at each size, with the pairing kept — every size solved against the same forty vectors, so the largest iterate is matched run for run. Averaged, the gap goes 3.83·10⁻¹⁵ at n = 20 to 4.46·10⁻¹⁵ at n = 80, a factor of 1.16 where 1.56 was predicted, and the exponent fitted against the mean step count over the seven sizes is 0.162. The reading under test requires 0.5. The averaged column climbs by sixteen per cent in total and does so without reversing, so what the single run showed as scatter conceals a real and very small trend — which is a different thing from the fifty-six per cent the reading requires, and is the honest form of the result.

The extra roundings are not small ones #

There is one way the result could be true and uninteresting: if the iterations a larger matrix adds happened at iterates so small that their roundings were negligible. A walk whose extra steps have length zero is not much of a counterexample, and the shape of this construction makes the worry a real one, since the iterate climbs from order one to 9,309 and the early steps are genuinely tiny.

The iterate norms say otherwise. At n = 20, thirty of the forty iterates the run passes through are within a factor of ten of the largest; at n = 80 it is seventy-eight of ninety-seven. The iterate climbs over the first dozen or so steps and then sits at its maximum for the rest of the run, because that maximum is not an excursion — it is the size of the solution itself, whose component along the small eigenvalue dominates every other. The extra iterations a larger matrix buys are spent at the top.

So the comparison is sharper than the table alone. Going from n = 20 to n = 80 commits 2.6 times as many roundings at the same magnitude — thirty full-size ones against seventy-eight — into a recurrence that keeps every one of them, and the accumulated difference between the reported residual and the real one moves by six per cent. Whatever the walk is walking over, it is not those.

The exponent is unmoved as well, which is the check that matters #

If the size were doing anything to the accumulation, the cleanest place for it to show is the exponent itself rather than any single value. The fit is made over ten decades of iterate size at each size of matrix, and it reads 0.443, 0.483, 0.494, 0.507, 0.507, 0.490 and 0.493 at n = 20, 30, 40, 50, 60, 70 and 80.

Seven independent fits, a fourfold range of matrix size, a 2.46-fold range of step count, and every one of them within 0.06 of a half. The half is a property of the accumulation and not of the problem it was first measured on, which is the claim the figure’s note made in its first clause and got right.

The same seven runs give the constant in front of it. Dividing the near-end gap by u·√(max‖x‖) gives 0.470, 0.355, 0.453, 0.427, 0.495, 0.492 and 0.498 — a number near a half at every size, with scatter and no order. The law the measurement supports is therefore that the gap is about u·√(max‖x‖), with the size of the matrix appearing nowhere in it.

And the other control moves it by four orders #

A negative result is worth only as much as the positive one beside it, because a quantity that refuses to move for one control might refuse to move for any. The second control settles that.

Holding the size at n = 20 and turning ε instead: the largest iterate goes from 9,309 to 9.31·10¹³, ten decades, while the step count goes from 39 to 56 — a factor of 1.44. The gap goes from 5.04·10⁻¹⁵ to 2.04·10⁻¹⁰, a factor of 4.06·10⁴. At n = 80 the same comparison reads 96 steps to 152, a factor of 1.58, against a gap that multiplies by 8.11·10⁴.

If the step count were the length, 1.44 more steps would buy a factor of 1.20 in the gap, and the measurement is forty thousand times that. The two controls therefore agree from opposite directions: the quantity that moves the gap is how far the iterates go, and the quantity that does not is how many steps it took to get there. The walk’s length is a distance, not a count.

That is a distinction this collection has had to make before in a different vocabulary. The rate that does not notice the size separates a constant belonging to a method from an exponent belonging to n, and does it the same way — by moving the size and watching which of two numbers follows.

The hardest stop does not separate them, and the condition number says why #

Every number above was read at the near end of the ε ladder, and that was a choice rather than a convenience. Made at the far end, the same comparison does not come out the same way, and the reason is a second thing the size moves.

At ε = 10⁻¹⁴, over the same forty right-hand sides, the mean gap goes from 2.21·10⁻¹⁰ at n = 20 to 4.31·10⁻¹⁰ at n = 80, a factor of 1.95 against a step-count prediction of √(151.8/55.7) = 1.65. That stop does not reject the reading under test; it overshoots what the reading predicts, which is not the same as confirming it and is certainly not a separation.

The condition number is why, and it is arithmetic rather than a hypothesis. The construction’s condition number is n/ε, so the size moves it as well as the step count, and how much that matters depends entirely on where ε has put it. At ε = 10⁻⁴ it runs from 2.0·10⁵ to 8.0·10⁵ against a reciprocal unit roundoff of 9.01·10¹⁵, ten orders of margin, and quadrupling it changes nothing about what the arithmetic can represent. At ε = 10⁻¹⁴ it runs from 2.0·10¹⁵ to 8.0·10¹⁵, and the largest of those is 1/u. The matrix at the far end and the largest size is numerically singular, so the sweep there is not moving one quantity at a time and cannot be read as a control.

The middle of the ladder says which reading survives when it is. At ε = 10⁻⁸ the condition number runs 2.0·10⁹ to 8.0·10⁹, seven orders inside the arithmetic; the mean gap goes 3.65·10⁻¹³ to 4.53·10⁻¹³, a factor of 1.24 where the step count predicts 1.67; and the exponent fitted against the mean iteration count is 0.211. The three stops give exponents of 0.162, 0.211 and 0.597 against a required 0.5, and the one that agrees is the one where the problem has run out of arithmetic. Two clean controls reject the step count and the third is not a control.

Where this stops being a statement about n #

The looseness of the bound has an n in it and the behaviour does not, so the two must diverge as the problem grows. At the near end of the sweep they do, and the column above shows it: the measured gap is 1.24·10⁻³ of the bound at n = 20 and 6.31·10⁻⁴ at n = 80. Over the forty right-hand sides the same share falls monotonically at n = 20, 30, 40, 50, 60 and 80 — 1.13·10⁻³, 9.80·10⁻⁴, 9.14·10⁻⁴, 8.24·10⁻⁴, 7.88·10⁻⁴ and 6.87·10⁻⁴ — so the bound is about 1.6 times looser on the largest of these matrices than on the smallest, at an identical iterate size.

The arithmetic behind that is plain. The bound is u·‖A‖·max‖x‖ relative to ‖b‖; ‖A‖ is n here, so it quadruples across the sweep, while ‖b‖ grows only as the square root of the size. The bound doubles, from 4.07·10⁻¹² to 8.46·10⁻¹². The thing it bounds does not move.

And the effect does not survive to the far end of the sweep, where the control fails for the reason just given. At ε = 10⁻¹⁴ the share of the bound reads 5.02·10⁻⁹, 6.43·10⁻⁹, 6.12·10⁻⁹, 7.30·10⁻⁹, 9.26·10⁻⁹, 4.62·10⁻⁹ and 5.12·10⁻⁹ across the seven sizes — a factor of two of scatter and no order at all. At that end the gap is nine orders below its bound and the run-to-run variation swamps a factor of 1.6. So the practical reading is a near-end one: the bound loosens with the size where it was tightest, and where it was already useless the size cannot make it more so.

What follows for anybody reading a solver #

The correction is not a curiosity about a fit. It changes what a reader should expect from three things they have control over, and in each case the expectation the step-count reading produces is wrong.

A longer run does not cost accuracy in the reported number. The natural inference from the note under the figure is that a run allowed to take three hundred iterations carries a worse-described answer than one that took a hundred, and it does not: at the same iterate size, 2.46 times the iterations bought six per cent. A run that is slow to converge is slow, and that is the whole of the complaint.

Cutting the iteration count does not close the gap. Preconditioning, restarting, a looser tolerance, a better initial guess — every one of them is bought and paid for as a reduction in steps, and none of them touches the quantity that sets the drift. What would touch it is anything that keeps the iterates small, which is a statement about the spectrum and the right-hand side rather than about the schedule. This is the same asymmetry a stopping test is a race records from the other side, where eleven different iteration counts on one problem all produce answers accurate to the tolerance asked for.

And the diagnostic to watch is the one already in the loop. The largest iterate norm costs an inner product the method has already computed, and it is the quantity the gap actually follows. The iteration count is free, prominent, printed by every solver ever written, and is not the number. That is the same shape as a small residual not being a small error: the quantity in front of the reader and the quantity governing the answer are two different things, and the visible one is visible because it is cheap.

The repair is indifferent to all of this, and that is the point #

The fix for a carried residual is to stop carrying it — assign b − Ax back into the recurrence every few steps — and the useful property of that repair is that none of the argument above changes what it costs or what it buys.

The cost is a fixed fraction of the products, so it scales with the run rather than with the drift, and the benefit is not an accumulation being prevented but an accumulation being discarded. Nothing in the repair needs to know how long the walk was or what it was a walk over, which is why it can be recommended without the measurement this essay is about — and why the measurement is still worth having, since the alternative advice a reader might reach for on the step-count reading is run fewer iterations, which costs convergence and buys nothing.

GMRES is the same lesson without the repair, because it never carries the quantity in the first place: its printed residual falls out of the projected problem at each step, re-derived from the whole basis, and it stays within a factor of 2.86 of its answer’s on three hostile matrices while the basis it is derived from has stopped being orthogonal. Nothing in a re-derived number accumulates, so nothing about it has a length.

What was measured and what is still asserted #

The claim published against this page is that the gap accumulates in proportion to what it accumulates against — a claim the bound licenses and the behaviour refuses. The refusal is fed the sweep and required to fail the assertion that the slope is 1, and it does, at every one of the seven sizes. A bound is an inequality, and reading its exponent as the behaviour’s is the error a bound every answer satisfies records in a different mechanism, where a correct summation bound sits 7,932 times above the spread it bounds.

What is measured here is narrower than the essay’s title suggests and should be stated at its own size. The gap is about u·√(max‖x‖); at two of the three stops on the ε ladder it depends on the number of steps with an exponent of 0.162 and 0.211 rather than a half, across seven sizes and forty right-hand sides each; the exponent against the iterate size is a half at all seven; and the bound, carrying an ‖A‖ that grows, loosens by a factor of 1.6 across a fourfold range of size at the near end of the sweep and by nothing measurable at the far end. The third stop is where the condition number reaches 1/u, and it is excluded as a control rather than explained away — a sweep that moves two things at once measures neither.

What is not measured is why. A walk whose steps are the roundings, each scaled by the iterate it occurred at, would predict a gap far larger than the one observed — the accumulation cancels against itself more than an independent-signs model allows, and this construction cannot say what the surviving terms are. That is the honest boundary, and it is the same one the vector that hides it reaches from the other end, where the condition number of a summation is computable and the actual error still depends on which vector arrived.

The useful half is settled regardless. A square root needs a length, the figure that established the exponent named the wrong one in a sentence under its own crank, and the length is a distance the iterates travelled rather than a count of the steps that took them there. Anyone reasoning about a long run from the number of iterations in it is reasoning from the quantity that was measured to move the gap by sixteen per cent, rather than from the one that moves it by forty thousand.

That is the same substitution one sequence and two recurrences finds between CGLS and LSQR, where two algebraically identical methods are separated by a property of a basis neither of them computes: the number in front of the reader is not always the number the result depends on, and the only way to find out is to move one and watch the other.