What a rebuild is worth

Two essays in this field have measured how fast an object ages — one on a factorisation kept past its date, one on where a drift has to land to cost anything. Neither of them has said what the ageing is worth, and it turns out that the ageing is the smaller half of the question.

Here is the whole of the other half. Reusing a preconditioner saves a rebuild and costs extra iterations. Whether that is a good trade depends on how many iterations one rebuild is worth, and that number is a property of the code rather than of the matrix: it is different for a dense Cholesky, an incomplete factorisation, a multigrid hierarchy and a fill-reducing ordering with a symbolic phase, and it can differ between them by two orders of magnitude on the same problem.

So the same sequence has several right answers, one per object, and none of them is discoverable from the sequence.

The currency #

Every reuse decision is a ratio, so the honest thing to do is to make the ratio the axis rather than bury it in a flop model.

A sequence is costed here in iteration-equivalents: the total number of preconditioned conjugate gradient iterations, plus the number of rebuilds times a setup ratio. The ratio is what one rebuild costs in units of one iteration, and for the objects a real code holds it runs over a wide range:

• a dense Cholesky at n = 80 is n³/3 against 4n² a step, which is n/12 — 6.7 iterations;
• an incomplete factorisation of a sparse operator is a few matrix passes, so a handful;
• a multigrid hierarchy — coarsening, interpolation operators, coarse-grid assembly — is tens;
• an ordering with a symbolic phase, on a distributed machine where it also decides which processor holds what, can be hundreds.

The measurement is the same twenty-four-member sequence, walked at eight fixed rebuild periods and four growth rules, and then costed at each of six setup ratios. Nothing about the sequence changes between the columns. Only the exchange rate does.

Reading the five drifts together says something the six columns of any one of them cannot.

Two of the six columns do not depend on the drift at all, and they are the two a cheap preconditioner lives in: at a setup ratio of 5 or 10 the answer is “every member” or “every other member” at every drift on the slider, a hundred-fold range. The drift only begins to matter at a setup ratio of 50, and even there it produces two answers rather than five.

And a hundred-fold range of drift produces three distinct rows. The middle two are identical and so are the last two, so the table is piecewise constant: a code that measured its drift to within a factor of three would choose the same period as one that measured it exactly.

That is the useful form of the essay’s claim. The setup ratio is what the decision turns on, and the drift is a quantity that needs bracketing rather than knowing — which is fortunate, because the setup ratio is a number a code can measure once with a stopwatch and the drift is a number it would have to infer from the sequence it is in the middle of.

The walk is a square root, which is the shape a cost amortised against a linear penalty always takes. At a drift of 10⁻² the optimum reads 1, 2, 3, 4, 6, 8 against setup ratios of 5, 10, 20, 50, 100, 200, and dividing by the square root of the ratio gives 0.45, 0.63, 0.67, 0.57, 0.60, 0.57 — flat to within a fifth across a forty-fold range. The same exponent turns up on the other axis further down this page, where the optimal period goes as the inverse square root of the drift; the two are measured with the other quantity held fixed, so the page does not claim the combined law, but they are the same shape arriving twice.

Six answers #

The optimum walks steadily from one to twelve. At the cheap end, rebuilding at every member is correct and there is no interesting decision to make — which is worth knowing, because it means the dense Cholesky of the previous essays, at 6.7, sits in the regime where the answer is always to rebuild and the reuse question does not arise.

At the expensive end the decision is worth a factor of nearly five: 1,008 against 4,850 for rebuilding every time. And never rebuilding at all is between four and seven times worse than the optimum at every ratio in the table, which is the other thing the figure says — the ageing is real, and no setup cost in this range makes ignoring it correct.

The free rule, and where it stops #

The previous essays each found a rule that reads something the iteration already computed and beats every constant — a tolerance in one case and a contraction ratio in the other. The obvious rule here is the same shape: rebuild when a solve takes more than γ times what the first solve after the last rebuild took. It needs no drift rate, no norm, no eigenvalues, and the quantity it reads is a count the loop already has.

At γ = 1.5 it rebuilds four times over the twenty-four members. Costed:

It wins in the middle and loses at both ends, and the reason is one line: it rebuilds four times whatever a rebuild costs. The number of rebuilds it chooses is a function of the ageing alone, because the ageing is all it can see. At a setup worth 5 the right answer is twenty-four rebuilds and it does four; at a setup worth 200 the right answer is two and it does four.

Why this is worth saying rather than fixing #

The obvious repair is to tell the rule the setup ratio. That is correct and it is also the end of the interesting part, because a rule that has been told the setup ratio is a rule with a tuned constant in it, and this field has spent three essays on why a tuned constant is the thing to avoid.

What is worth carrying instead is the shape of the failure, because it is general.

A free measurement is free because something else is paying for it. The residual ratio in a Newton iteration is free because the iteration computes residuals; it happens to be the exact quantity the tolerance decision needs, and that is luck rather than design. The contraction ratio of a chord iteration is free for the same reason and is again exactly right, because the decision there is “is this factorisation still working” and the ratio is the answer.

The iteration count of a preconditioned solve is free too, and it is only half of what the decision needs. The other half — what a rebuild costs — is not a quantity any solve produces, is not visible in any residual, and does not appear anywhere in the iteration. No amount of watching the iteration more carefully will reveal it.

So the field’s reading, stated three essays ago, has a boundary and this is it: a rule that recomputes its decision from what the iteration is doing beats a constant when the decision is entirely about what the iteration is doing. Here it is half about the code, and the rule is half right.

Never rebuilding is the worst policy at every ratio #

One column of the table deserves more attention than it usually gets, because it contradicts the way this decision is normally discussed.

The “never rebuild” column runs 1,161, 1,166, 1,176, 1,206, 1,256, 1,356 — barely moving, because a policy with one rebuild in it barely notices what a rebuild costs. And it is between four and seven times the optimum at every single ratio.

That is worth stating plainly because the usual framing of preconditioner reuse is how long it can be kept before something breaks, as though keeping it were the default and rebuilding were the expense. On this measurement the default is wrong. The sequence drifts, the iteration count climbs from 18 to 52, and a policy that never pays for a rebuild pays for it in iterations several times over — even when a rebuild is worth two hundred of them.

There is a regime where never rebuilding is correct, and the last section of this essay is about it. It is the regime where the sequence barely drifts, and the honest summary of the whole table is that both defaults are wrong most of the time and the decision is a measurement.

Two rules, two objects, two outcomes #

It is worth putting this essay’s rule beside the one from the essay on a kept factorisation, because they are the same idea and only one of them works.

Both read a quantity the iteration produces for free. Both avoid a tuned constant. Both are scale-free. The chord rule wins at every drift rate measured; the growth rule wins at two setup ratios out of six.

The difference is not the quality of the rule, it is the shape of the failure it is guarding against. A stale factorisation stops working, and a rule that watches for it not working is watching the right thing: the cost of being wrong is unbounded on one side and small on the other, so the rule only has to detect the cliff. A stale preconditioner costs more, symmetrically, and detecting that it costs more is only half of a comparison whose other half is off-stage.

A rule can be free and right when the decision is one-sided. When both directions cost, the rule needs both prices, and a free measurement gives it one.

This is where the other square root is. Across that figure’s own slider the cheapest fixed period reads 20, 10, 5 and 3 at drifts of 10⁻³, 3.2·10⁻³, 10⁻² and 3.2·10⁻², and multiplying each by the square root of its drift gives 0.632, 0.566, 0.500 and 0.537 — flat to within a fifth while the drift moves by a factor of thirty-two. So the period goes as the inverse square root of the drift here, and as the square root of the setup ratio in the table above, each measured with the other held fixed.

Both are the same arithmetic seen from two sides: a fixed cost paid once and amortised over a period, against a penalty that accumulates linearly across that period. Minimising the sum puts the optimum at the square root of their ratio, which is why neither axis produces a sharp optimum — the curve near a square-root minimum is flat, and being a factor of two out costs about a quarter.

The sequence that needs no rule #

There is one more case and it is worth drawing, because it is the regime most sequences are actually in and because the rule is wrong there too.

Slow the drift down by four orders of magnitude and the preconditioner never goes stale: one build serves all twenty-four members, never rebuilding is the cheapest fixed policy at every setup ratio, and every rebuild is pure waste.

The growth rule still rebuilds twice. Not because it detected ageing — there is none — but because the iteration count moves with the right-hand side. Two solves of the same matrix to the same tolerance take different numbers of steps depending on where b lands in the spectrum, and a rule watching that count cannot tell the variation from the ageing.

That is a third way to be fooled, and it is the one most likely to bite in practice, because the right-hand sides in a real sequence are not drawn from one distribution either.

Reading the table for a real code #

The figure is a staircase over a synthetic ratio, and it is worth saying how somebody with an actual solver would use it, because the answer is not to read a period off the chart.

The ratio is measurable directly and cheaply: time one rebuild, time one preconditioned iteration, and divide. That is two measurements a profiler already has, and it is the only site-specific number the whole decision needs. Everything else on the figure — how fast the sequence drifts, how many members there are — is a property of the problem being solved rather than of the code, and the figure shows that the answer moves far more with the ratio than with either of those.

Two consequences follow that are worth stating separately from the measurement.

The right period is not portable between codes. The same sequence solved by two solvers with different setup costs has two different right answers, and a number carried across from one to the other is wrong by however far apart their ratios are — which the table puts at a factor of five in total cost at the extremes.

And it is not portable between machines. The ratio is a ratio of two timings, and the two scale differently: a setup that is largely symbolic and serial does not accelerate the way an iteration made of matrix–vector products does. A period tuned on one machine is a period tuned for that machine’s ratio, and this collection’s cost field has spent an entire run establishing that such numbers do not travel.

The constant the rule was supposed to avoid #

The growth rule arrived here as the one that needs nothing tuned: no drift rate, no norm, no setup ratio, only a count the loop already has. It does need one number, which is γ, and it is worth asking what the rule does at the other values of it — because the library sweeps four and only one of them does anything at all.

At γ = 1.5 the rule rebuilds four times and spends 308 iterations, which is the row the tables above price. At γ = 2 it rebuilds twice and spends 1,058. At γ = 3 and at γ = 5 it rebuilds once — the initial build, which is not a decision — and spends 1,156, which is not merely a poor policy: it is the never rebuild column of the first table, to the iteration. Two of the four settings of the free rule are the worst fixed policy in this essay wearing a different name, and a third is within nine per cent of it.

The reason is a single number and it is a close-run thing. Never rebuilt, this sequence’s iteration count climbs 27, 35, 38, 42, 44, 46 … 53, 55 — from 27 at the first member to 55 at the twenty-fourth, a factor of 2.037. A rule set to fire at twice the fresh count therefore fires once, at the very end, on a preconditioner that has been going stale for twenty-three members; a rule set at three times never fires. The whole difference between a policy costing 508 iteration-equivalents at a setup ratio of 50 and one costing 1,206 is whether γ sits below 2.04 or above it, and nothing the iteration computes says where 2.04 is. It is a property of the drift rate, which is the quantity the rule was adopted in order not to need.

So the rule is not free of tuned constants. It has moved the constant from a period to a threshold, and that move is a real improvement — a threshold in a dimensionless ratio transfers between sequences in a way that a period counted in members does not, which is exactly the argument the tolerance rule and the chord rule make, and make correctly. But a scale-free constant is still a constant, and this one has the sequence’s own drift rate deciding which side of it the run falls on.

A rule that reacts is always one member late #

There is a second cost, structural rather than tuned, and it is visible in the per-member counts rather than in any total.

A fixed period rebuilds before the solve at member t, on that member’s own matrix. The factorisation is therefore exact for the system it is about to be handed, and the member costs one iteration. Walked at a period of six, that is what the sequence does: 27, 35, 38, 42, 44, 46, 1, 7, 8, 9, 9, 10, 1, 6, 6, 7, 7, 8, 1, 5, 6, 6, 6, 7. Every rebuild buys a free member.

The growth rule cannot collect that, and not because it is written badly. It fires on evidence, and the evidence is a solve that has already been slow. So it rebuilds after member t, on Aₜ, and the fresh factorisation first meets Aₜ₊₁ — one drift step out of date before it is ever used. Its three restarts cost 8, 6 and 5 iterations where a scheduled rebuild’s cost 1.

Sixteen iteration-equivalents over the run, then, spent purely on being late. That is a small number and it is the wrong size to ignore: at a setup ratio of 100 the rule beats the best fixed period by nineteen. Almost the whole of its winning margin at the expensive end is the size of a defect it has no way to remove, because removing it would mean rebuilding before the slow solve that is the only evidence a rebuild was due. A reactive rule pays one member of staleness per decision, and it makes its decisions exactly where a rebuild is dearest.

Where a wrong period actually costs something #

One more reading, and it inverts the anxiety this decision usually attracts.

At a setup ratio of 200 the neighbouring period costs 1.9% more than the best one — every twelve against every eight, 1,008 against 1,027 — and both periods either side of the optimum are within two per cent of it at every ratio from 50 upwards. At a setup ratio of 5 the neighbouring period costs 17% more, and at 10 it costs 6.6%.

So the flat part of the curve is at the expensive end and the sharp part is at the cheap end, which is the reverse of where the worry usually goes. A code holding a multigrid hierarchy can be wrong by a factor in its rebuild period and lose two per cent; a code holding an object cheap enough to rebuild at every member loses a sixth of its run by rebuilding at every second one instead. The decision that is worth the most in relative terms is the one nobody treats as a decision — and the essay on where a drift lands makes the same point one level down, that the quantity moving the answer is not the quantity being watched.

That is also the practical reading for a code that solves the same problem repeatedly. Measure the ratio, and if it comes back small, stop thinking about the period and rebuild every time; the flatness is at the other end of the axis, and it is not where the cheap object lives.

What is asserted #

Four things, each with a case it must refuse.

That the optimum never falls as the setup gets more expensive — one, two, three, six, eight, twelve — and that it moves from rebuilding at every member to rebuilding once in twelve across the range measured.

That never rebuilding is several times worse than the optimum at every ratio, so the essay is not an argument for keeping things.

That the growth rule beats the best fixed period at 50 and 100 and loses at 5 and 200, which is the refusal: fed the claim that it wins everywhere, the assertion fails.

And that on a sequence with essentially no drift, the rule rebuilds anyway — which is asserted in the direction that says the rule is fooled rather than in the direction that says it agrees.