A speedup with a ceiling of its own

A preconditioner is sold as a factor. It takes a solve from a hundred and seventy-nine steps to ten, and the number quoted — eighteen — is the ratio of two counts. Everything this field has measured about circulant preconditioning has been measured on the second of those counts: which circulant, whether it stays positive definite, how tightly it clusters the spectrum, what the count does as the matrix grows.

The first count has never been examined at all. It appears on every figure in the field — the dashed line labelled no preconditioner, drawn for scale, above whatever the preconditioners are doing — and no essay reads it. That is the curve this one is about, and it has a property that decides how large the advertised factor is allowed to be: it stops climbing.

The reason is short enough to state before it is measured. Conjugate gradients on a symmetric positive definite system take about ½√κ·ln(2/tol) steps. On the Kac–Murdock–Szegő family ρ^|i−j| the condition number does not grow without limit: it climbs to Szegő’s ((1+ρ)/(1−ρ))² and stops, which is the field’s founding measurement. A bounded κ gives a bounded step count, so the numerator of every speedup on this family is bounded, and therefore so is the speedup.

The numerator stops, and the stopping is visible on the figure #

At ρ = 0.5 the unpreconditioned count reads 15, 22, 29, 28, 30 and 30 as the matrix goes from sixteen rows to five hundred and twelve. It climbs steeply for two doublings, then falls by a step between n = 64 and n = 128, and then does not move at all across the last three sizes drawn. That is not a plateau being approached; it is a plateau being sat on, at a size any code would call small.

Past the right-hand edge of the figure it does not resume. Continuing the same solve at every doubling out to n = 16,384 gives 29, 28, 26, 27 and 25 — the count is not merely flat but gently falling, and the fall is real rather than noise, since it survives a factor of thirty-two in the problem size. A matrix with 268 million entries is solved to a relative residual of 10⁻¹⁰ in twenty-five iterations of a method that was given no preconditioner whatever.

Read that against the other column. The averaged circulant of the construction that cannot be indefinite takes 8, 8, 7, 6, 6, 5 steps over the same range, and 5, 5, 5, 4, 4 at each doubling out to n = 16,384. It is winning, and it is winning by a factor that has stopped growing, because both of its terms have stopped moving.

The interesting sentence is therefore not the preconditioned count is flat — that is the theorem, and this field has already measured it — but both counts are flat, and the second one is flat for a reason that has nothing to do with preconditioning. The dashed curve is flat because the family ran out of conditioning, and it would be flat if no preconditioner had ever been written.

Where the ceiling comes from #

The condition number of the n×n section of this family is the quantity that decides everything above, and it has an asymptotic value in closed form.

At ρ = 0.5 the limit is exactly 9, and the sections reach it fast: κ measures 8.462 at n = 16, which is 94.0% of the limit, then 8.839, 8.956, 8.988 and 8.997 — 98.2%, 99.5%, 99.9% and 100.0% to the digits printed. So by n = 64 the matrix is as badly conditioned as any member of the family will ever be, and there is nothing left for a step count to grow with.

That is the mechanism in full, and it is worth being precise about which direction it runs. The step count is not flat because conjugate gradients are doing something clever at large n. It is flat because the problem stops getting harder, and the method is reading a quantity that has converged. Everything the essay that measured that convergence said about a limit approached from below and never attained transfers directly, one derivative down: a κ within a tenth of a per cent of its limit produces a step count within a step or two of its own.

The connection between the two is the classical bound, which this collection has already priced as a bound rather than an estimate: after k steps the error is reduced by roughly ((√κ − 1)/(√κ + 1))^k, so reaching a tolerance costs about ½√κ·ln(2/tol) steps. At the limiting κ = 9 and the tolerance of 10⁻¹⁰ every count here is measured at, that is 35.6 steps. The measured ceiling is 30.

The ceiling has a value at every correlation, and the bound gives it to a fifth #

One correlation is an anecdote. Running the same measurement across the range gives a ceiling for each, and a check on whether the bound predicts it.

At ρ = 0.7 the dashed curve arrives at its ceiling later and higher: 19, 29, 38, 46, 56, 57 across the figure, then 56, 54, 53, 52 and 51 out to n = 16,384. The limiting κ is 32.11, the bound is 67.2 steps, and the highest count measured anywhere on the sweep is 57.

The same arithmetic at six correlations:

The last column is the result. Across a factor of a hundred and seventy in the condition number the measured ceiling sits between 81.3% and 84.8% of what the bound permits, which is a narrower band than that bound usually deserves. On the model problem of the iterative field the same expression overpredicts by an order of magnitude — 400 steps permitted against 40 taken — because its eigenvalues are clustered and the bound throws away everything about a spectrum except its two ends. Here the eigenvalues fill the range of the symbol rather than bunching inside it, so the two ends are very nearly the whole story and the bound is nearly tight.

Two caveats belong with that number rather than after it. The bound is stated for the error in the energy norm and the counts here stop on a relative residual, and those two quantities are not the same one — the essay above measures a factor of 2.5 between them over a run, which is the slack this comparison carries. And highest count measured is not quite ceiling at ρ = 0.95, where the sequence 331, 365, 370, 376 is still creeping upward at the largest size run.

The speedup a code can honestly claim #

With both terms measured, the advertised factor can be given a value rather than an adjective.

At n = 512, the largest size on these figures, the ratio of the unpreconditioned count to the averaged circulant’s runs 6.0, 6.7, 9.5, 14.3, 21.4 and 24.3 at ρ = 0.5, 0.6, 0.7, 0.8, 0.9 and 0.95. Those are the numbers a code solving a five-hundred-row system is entitled to quote, and they are the honest form of a claim usually made as orders of magnitude: at half correlation the preconditioner is worth a factor of six, and six is not an order of magnitude.

Pushing both counts to their own ceilings gives the largest factor the family can ever produce. Taking the highest unpreconditioned count against the highest preconditioned one over sizes from 2,048 to 16,384: 5.6, 7.6, 10.8, 17.4, 31.2 and 47.0 at the same six correlations. So the factor does keep growing with ρ, and it does not keep growing with n.

At the gentle end it does not even reach its n = 512 value and stay there. The ratio at ρ = 0.5 reads 6.0 at n = 512, then 5.8 at 1,024 and 5.6 at 2,048 — it peaks and comes back down, because the numerator is falling slightly while the denominator has already bottomed out at four or five steps. A speedup measured at one size and reported as the method’s is being reported at its maximum, and the direction of the error is the flattering one.

This is the shape a ratio whose numerator saturates always has, and the practical reading is about provisioning rather than about credit. A code that budgets iterations by assuming its preconditioner buys a factor that grows with n has budgeted for something that does not happen on this family, and it will be wrong in the direction of allocating too little unpreconditioned work as a fallback.

The other circulant says the same thing about the choice of construction #

The figures carry a third curve as well, and once the ceiling is in view it reads differently from the way its own essay read it. At ρ = 0.5 the wrapped circulant — the one that discards half of each diagonal instead of averaging the two — takes 7, 4, 3, 3, 3 and 3 steps across the six sizes. It is better than the averaged construction at every size drawn, and it is positive definite throughout — its smallest eigenvalue is 0.3281 at n = 16 and settles at exactly 0.3333 — so nothing about the sign change that made it dangerous is in play at this correlation.

Three steps against an unpreconditioned thirty is a factor of ten, against the averaged circulant’s six. That is a real difference between the two constructions and it is a smaller difference than it sounds, because both of them are dividing into a numerator that has stopped. Choosing the better circulant at ρ = 0.5 moves the advertised factor from six to ten; choosing a harder problem moves it from six to forty-seven. The correlation decides an order of magnitude and the construction decides most of a factor of two, and only the second of those is usually presented as the engineering decision.

The two constructions diverge sharply exactly where the wrapped one is indefinite, which is the other end of the range: at ρ = 0.95 it reads 21, 55, 117, 122, 9 and 5 against the averaged circulant’s 7, 8, 9, 10, 10 and 9. So the choice matters where the ceiling has not arrived, and where it has arrived the two are separated by a few steps out of thirty.

Where the ceiling has not arrived yet #

The argument so far could be read as saying the unpreconditioned count is uninteresting at any size, and at the hard end of the family that is false.

At ρ = 0.95 the dashed curve climbs at every size on the figure and keeps climbing past it: 219 at n = 512, then 281, 331, 365, 370 and 376. The limiting κ is 1,521 and the 128×128 section has reached only 87.9% of it, so the conditioning still has room to grow, and the count grows with it. The ceiling exists — the bound puts it near 463 and the measurement is flattening towards 376 — but no size a figure can draw is anywhere near it.

That is what makes the ceiling a fact about the correlation rather than about the method. At ρ = 0.5 it has arrived by n = 64; at ρ = 0.95 it has not arrived by n = 16,384. The same sentence — the unpreconditioned count stops climbing — is a description of the whole figure at one end of the range and a promise about a size nobody runs at the other, which is exactly the distinction the verdict for a limit nobody reaches was created to mark, applied here to the count instead of to the condition number that governs it.

So a speedup quoted at ρ = 0.95 and n = 512 is quoted against a numerator that has not finished growing, and it will get better. A speedup quoted at ρ = 0.5 and n = 512 is quoted against a numerator that finished growing eight sizes ago, and it will get slightly worse.

The flat curve is a hump #

The preconditioned count deserves the same reading, and it does not survive it either.

The preconditioned count is described everywhere, including by this field’s own essays, as flat. At ρ = 0.9 it reads 7, 9, 10, 10, 9, 7 across a factor of thirty-two in the problem size. That is not flat. It rises by three steps, holds, and falls by three steps, and the two ends are equal — the curve is a hump, and a summary of it as between seven and ten is true and discards the shape.

The maximum moves right as the correlation rises. At ρ = 0.7 and 0.8 the counts read 8, 9, 8, 7, 7, 6 and 8, 9, 8, 8, 7, 6, peaking at n = 32. At ρ = 0.9 the peak is at n = 64 and 128; at ρ = 0.95 the counts are 7, 8, 9, 10, 10, 9 and the peak has moved to n = 128 and 256; at ρ = 0.97 they read 6, 8, 9, 10, 10, 10 and the peak has left the figure altogether. So a slate of sizes chosen to straddle the peak reports a rising count, one chosen above it reports a falling count, and one chosen either side of it reports a flat one. All three are the same curve.

Two measured quantities pull in opposite directions, and the hump is where they cross. The first is the preconditioned condition number. At ρ = 0.9 the spectrum of C⁻¹T has κ = 10.74, 14.63, 16.71, 17.74, 18.33 and 18.66 at n = 16 to 512 — rising steeply at first and then saturating, since it has its own limit for the same reason the unpreconditioned one does. The second is the clustering. The radius of the smallest interval around one holding all but two of the eigenvalues reads 0.3254, 0.2223, 0.1288, 0.0717, 0.0374 and 0.0187 — halving at every doubling of n, without saturating at all.

Early on the condition number is growing by 56% across two doublings and the cluster is only tightening by a factor of 2.5, so the count rises. Later the condition number moves by 5% while the cluster tightens by a factor of 3.8, so the count falls. The turning point is where those two rates cross, and it moves right with ρ because a larger limiting κ takes longer to reach.

The check on that account is the gentle end, where one of the two effects is absent. At ρ = 0.5 the preconditioned condition number reads 2.78, 2.88, 2.94, 2.97, 2.98 and 2.99 — essentially converged at the smallest size drawn — while the cluster radius still halves at every doubling, 0.0767 down to 0.0026. With nothing pushing up and the same thing pulling down, there is no hump: the count falls monotonically, 8, 8, 7, 6, 6, 5. The prediction and the measurement agree, and the quantity that separates the two cases is the one this whole essay is about.

One number in that account is worth stating on its own. The count of eigenvalues lying outside a tenth of one is exactly two, at every size, at ρ = 0.5 — while the share inside rises from 87.5% to 99.6%. The cluster is not acquiring members; the outliers are a fixed pair and everything else is closing in on them. That is the mechanism behind a clustering result measured in two dimensions and found not to hold, seen from the side where it does.

The norm that chooses the preconditioner moves the wrong way #

The averaged circulant is chosen by a norm. It is the orthogonal projection of T onto the circulants, so it is the minimiser of ‖C − T‖ in the Frobenius norm, and that distance is a number available at every size. It is worth asking whether it tracks any of the above, because it is the quantity the construction is defined by.

It does not track any of it. At ρ = 0.9 the minimiser’s own relative distance to T reads 0.1246, 0.1739, 0.2112, 0.2572 and 0.2765 at n = 8, 12, 16, 24 and 32: the nearest circulant to the matrix gets further from it as the matrix grows, by a factor of 2.2 across that range, while the speedup the same preconditioner delivers rises from 2.9 to 3.9. Continuing past the sizes the figure can draw, the distance turns around — 0.2545, 0.1880, 0.1343 and 0.0955 at n = 64 to 512 — so the norm is itself a hump, peaking near n = 32, while the speedup climbs monotonically to 21.4 and then to 31.2.

So the quantity that selects the preconditioner is non-monotone in n, peaks in a different place from the step count, and moves in the opposite direction over a third of the range. It is a correct answer to which circulant is nearest and it is not a figure of merit, in the same way that a nearest-in-norm construction can be exactly optimal for a distance nobody was asking about. What the step count reads is the spectrum of C⁻¹T, which the distance cannot see.

What follows for anything that quotes a factor #

A speedup needs its size and its correlation attached. The same preconditioner on the same family is worth 6.0 or 24.3 depending only on ρ, and at fixed ρ it is worth different factors at different n. A factor quoted bare is a measurement of the slate it was run on.

The unpreconditioned count is not a fallback plan. At ρ = 0.5 and n = 16,384 it is twenty-five iterations of a method that touches 2n − 1 numbers per step through the embedding that makes a Toeplitz product exact. Five against twenty-five is worth having and it is not the difference between feasible and infeasible, which is how a preconditioner is usually justified.

A preconditioner earns its keep at the hard end. At ρ = 0.95 the unpreconditioned count is 376 and still climbing at the largest size run, and nine steps against it is the case the construction exists for. The factor grows with the correlation, which is the axis it should be quoted along.

And a step count that does not notice n is a different claim from one that has stopped noticing. The V-cycle’s rate genuinely does not depend on the grid, by a mechanism that holds at every size. The flatness here is two curves that both ran out of room, and one of them would be flat with no preconditioner in the code at all. A summary statistic that cannot tell those apart is a number that decides nothing.

What the refusal is fed #

The claim this essay refuses is that the saving from circulant preconditioning grows with the problem, and the refusal is fed the case where the ratio of two step counts carries no information at all.

At ρ = 0.05 the limiting condition number is 1.222, and the counts confirm what that leaves to do: the unpreconditioned solve takes 8, 8, 8 and 7 steps at n = 16 to 128 and the averaged circulant takes 5 at every one of them. There is no conditioning for a preconditioner to remove, both counts are small constants, and their ratio — a flat 1.6 — is a number that would be reported as a speedup and would measure nothing. The generator is required to reject that comparison rather than to draw it, which is the same habit that has a small residual refused as evidence of a small error: a quantity is only a measurement where the thing it divides by is doing work.

The positive half of the refusal is the table above. The saving is a ratio, the numerator has a ceiling fixed by ρ alone, and at ρ = 0.5 the ratio has already passed its maximum by n = 1,024. A claim that it grows with the problem is true at ρ = 0.95 and false at ρ = 0.5, on the same family, with the same preconditioner, measured the same way.