The penalty for keeping it is a ratio

Every rebuild policy in this field is a comparison between two numbers: what the next member of a sequence costs with the factorisation already in hand, and what it would cost with a fresh one. A rule fires when the first has grown far enough past the second to pay for the rebuild. Both are iteration counts, both are measured on the same operator, and the awkwardness that the essay on where a drift has to land ends on is that the second one is not available without doing the thing the policy exists to avoid.

That is a difficulty about one member of one sequence. Underneath it sits a different question, and it is the one that decides whether a rule written once can be shipped at all: which of the two numbers depends on the size of the problem? If both do, a threshold calibrated on a test case is worth nothing on the production case, and every code that grows its mesh has to recalibrate. If the comparison between them does not, the calibration is a one-off and the number that came off the small problem is the number to keep.

There is a form of the answer already in this collection, asserted rather than swept. The incomplete-factorisation figure carries a caption that reads, in full:

The same comparison on a larger grid, where both curves lift and the separation between them does not change.

The first half of that is right and is measured below. The second half is the interesting one, and it turns on what “the separation” means. Two curves can be separated by a difference or by a ratio, the two readings disagree, and on this sequence they disagree by enough to matter and in opposite directions.

Two readings of one separation #

The operator is the five-point Laplacian on a square grid, and the drift is an anisotropy: the two directions stop being equally weighted, ε falling as 1/(1 + t/4)² over nineteen members, from 1 to 0.0331. The sparsity pattern never changes, which is exactly the situation in which a factorisation gets kept — nothing about the new matrix makes the old factor inapplicable, so nothing complains. The essay on how much fill elimination creates explains why an incomplete factorisation is what a code holds here in the first place, and the anisotropy itself is the object the essay on coarsening one direction treats as a problem rather than as a perturbation.

The caption’s own essay contains both of the numbers needed to test it, at two different sizes. Its body prints the sequences at 144 unknowns: the kept factorisation ends at 52 iterations, the rebuilt one at 13. Its figure draws 256 unknowns, where the kept one ends at 55 and the rebuilt one at 17.

Read as a difference, the separation goes from 39 to 38 — a fall of 2.6 per cent, which is as close to “does not change” as two integer counts can come. Read as a ratio, it goes from 4.00 to 3.24, a fall of 19 per cent. The caption is nearly exactly right under one reading and out by a fifth under the other, and nothing in it says which was meant.

Two sizes cannot settle that, because two points fit anything. What settles it is a sweep, and the generator has a grid side to sweep over.

Six grids, and neither quantity survives #

Six grid sides from 8 to 16 give 64, 100, 121, 169, 225 and 256 unknowns — a fourfold range in the size of the problem, on the same drift, with the same nineteen members and the same tolerance. Both curves lift, as the caption says. The kept factorisation’s first-member count runs 14, 16, 17, 20, 21, 23 and its last-member count runs 40, 46, 50, 52, 55, 55; the rebuilt one ends at 10, 12, 13, 15, 16, 17.

The two readings of the separation then run:

Neither column is flat. The difference spans 30 to 39, a spread of 30 per cent, and it rises with the grid. The ratio spans 3.24 to 4.00, a spread of 24 per cent, and it falls. Fitted against the number of unknowns on log axes over all nine grid sides from 8 to 16, the difference has a slope of +0.169 and the ratio a slope of −0.157: two quantities drifting at almost exactly the same rate, in opposite directions, and a claim of invariance is available for neither.

So the honest verdict on the caption is that it is right about the lifting and wrong about the separation under either reading, by a fifth in one and by a quarter in the other. That does not touch anything else on that page: the finding there is that a drift’s cost is decided by where in the spectrum it lands rather than by its norm, which is a statement about one matrix at one size and is measured on a different figure entirely. This is a caption about a figure the argument passes through, and it is the kind of claim that is easy to write once and never sweep.

Where the nineteen per cent comes from #

The fall is not noise and it is not a fit. It is the quotient of two growth rates, and the arithmetic closes exactly.

Over the fourfold range in unknowns the kept factorisation’s last-member count goes from 40 to 55, a factor of 1.375. The rebuilt one goes from 10 to 17, a factor of 1.70. The ratio at the end of the sequence is kept over rebuilt, so its own change is 1.375 divided by 1.70, which is 0.8088 — and 4.00 multiplied by 0.8088 is 3.235, which is 55/17 to every digit the counts carry.

The ratio falls because the rebuilt count rises faster than the kept one, which is worth stating in the opposite order to the way it reads. It is not that staleness gets cheaper on a bigger grid. It is that a fresh incomplete factorisation gets worse faster than a stale one does, and the reason is that the stale one is already carrying most of the damage the anisotropy can do to it.

The fitted slopes against the number of unknowns say the same thing in one line. The count at the first member — where kept and rebuilt are the same object by construction, so this is the grid’s own contribution and nothing else — has slope 0.358. The rebuilt count at the last member has slope 0.386, which is the same growth with the easier operator’s small discount on it. The kept count at the last member has slope 0.229. The drift’s contribution saturates as the grid grows and the grid’s does not, so the two effects separate, and the ratio is the quantity in which they separate visibly.

That also explains why the sequence of ratios is not monotone. It reads 4.00, 3.83, 3.85, 3.47, 3.44, 3.24, and the two rises in it are integer artefacts rather than reversals: the counts are whole numbers between 10 and 55, so a single iteration either way moves the ratio by two to ten per cent. Averaged over the nine grid sides the drift is clean; read as six points it is a staircase, and a rule fitted to any two adjacent points would be fitting the staircase.

The verdict depends on where in the sequence it is read #

Everything above is read at the last member, which is the worst case and the one a figure’s badge naturally reports. It is not the member a policy spends most of its time in. Reading the same comparison earlier changes the size of the drift and does not change its sign, and the change is large enough to be worth having.

At the tenth of the nineteen members, where ε has fallen to 0.0947 rather than 0.0331, the ratio across the six grids reads 2.50, 2.29, 2.33, 2.28, 2.32, 2.24 — a spread of 12 per cent, half what the last member gives. The difference at that same member reads 18, 18, 20, 23, 25, 26: a spread of 44 per cent, half again as large as the last member’s. Summed over the whole sequence, the kept run costs 557, 630, 660, 722, 781 and 811 iterations against a rebuilt run’s 233, 271, 290, 330, 366 and 388, for ratios of 2.39, 2.32, 2.28, 2.19, 2.13, 2.09 — a spread of 14 per cent — and differences of 324, 359, 370, 392, 415 and 423, a spread of 31 per cent.

Three readings, three margins, and the ordering is the same in all of them. The ratio transfers across a fourfold change in the size of the problem to within 12, 14 or 24 per cent depending on where it is taken, and the difference to within 31, 30 or 44. Whichever member the reading is taken at, the ratio is the more nearly dimensionless of the two, and the earlier the reading the wider the margin between them. That is the sense in which the penalty for keeping a factorisation is a ratio: not that the ratio is constant, because it is not, but that it is the form in which the penalty most nearly travels between problem sizes.

A policy is not paid in ratios #

Which leaves the practical claim, and it does not follow from any of the above. A code does not spend ratios. It spends iterations and it spends factorisations, and the quantity that decides a rebuild period is the difference between the kept and rebuilt counts, weighed against what a rebuild costs. The difference is the column that transfers worse.

So the transfer has to be measured rather than deduced. The same six sequences are walked again at fixed rebuild periods from every member to every fifteenth, costed in iteration-equivalents — total preconditioned iterations, plus the number of rebuilds times what one rebuild is worth — which is the currency the essay on what a rebuild is worth sets up and sweeps over the setup cost. Here the setup cost is a column and the size of the problem is the axis, which is the axis that essay holds fixed. The cheapest fixed period, by grid and by setup cost:

Three of the six columns do not move at all, and the other three move by one member once each. A period chosen on the smallest grid and run on the largest costs 0.23, 0.66, 0, 4.32, 0 and 0 per cent more than that grid’s own best policy, across the six setup ratios. The worst case is a setup worth 50 iterations, where 64 unknowns say rebuild every tenth member and 256 unknowns want every seventh: 628 iteration-equivalents against 602. Four per cent is the whole price of calibrating on a problem a quarter of the size. That is the practical statement the caption was reaching for, and it survives the caption being wrong.

It survives with one correction, and the correction is the reason to sweep rather than reason. The ratio falls with the grid, which invites the conclusion that a large problem tolerates a longer rebuild period than a small one — staleness costing relatively less. The measurement says the opposite: where the period moves at all it moves down, from ten members to seven and from five to four. It moves down because the policy is priced in the difference, which rises with the grid, against a setup cost held fixed in iteration-equivalents. A rebuild on the 256-unknown grid saves 38 iterations at the last member where on the 64-unknown grid it saves 30, and it costs the same 50. So a policy calibrated small rebuilds slightly too rarely at scale, not too often, and the falling ratio predicts the sign wrongly while the rising difference predicts it correctly.

That is a small error with a large moral attached. The ratio is the better diagnostic and the difference is where the money is, and the two point different ways.

The same two numbers on an object that is not a preconditioner #

The shape is not particular to an incomplete Cholesky. A chord iteration holds a factorisation of a Jacobian and reuses it across the members of a continuation, which is the object the essay on a factorisation kept past its date measures, and it presents the same two candidate summaries. Rebuilt every sixth member, the run costs four factorisations and 202 chord steps against twenty factorisations and 102 steps for the fresh policy.

Read as a ratio, the worst member costs 20 steps against a fresh factor’s 5 — a factor of four, which is the same number the incomplete Cholesky reaches at the small end of its grid sweep. Read as a difference, the same member costs fifteen extra steps, and the whole run costs a hundred extra steps for sixteen saved factorisations. The loud number is the ratio at the worst member and the number that is actually paid is the difference summed over the run, and they are as far apart here as they are above.

Two objects with nothing in common but the practice of keeping something expensive, and in both the comparison a reader remembers is not the comparison a code is billed for.

The refusal #

The claim worth publishing against a nearly-dimensionless ratio is the one a dimensionless quantity invites: that a kept factorisation ages because it is old, so the penalty is a function of how long it has been held. Every figure above is consistent with that reading — the curves separate steadily with the member index, and the member index is time.

It is refused by holding the operator still. The same nineteen-member sweep is run with the drift rate set to zero, so every member is the same matrix and only the right-hand side changes. On 144 unknowns the kept factorisation costs 18 preconditioned iterations at the first member and 18 at the nineteenth, and the ratio against a fresh factorisation is 1.000 at every one of them. The assertion that a kept factorisation more than doubles its count over the sequence is fed that run and fails, which is what it is there for.

What the undrifting run does show is a wobble: the counts read 18, 18, 19, 19, 18 and back, on an operator that has not moved at all. That is the right-hand side, not the factorisation, and it is the noise floor under every ageing measurement on this page — a rule watching iteration counts alone cannot tell a fresh right-hand side from an hour of ageing, which is the failure the essay on what a rebuild is worth prices. Here it is one iteration in nineteen and the drift is thirty; at a slower drift the two would be the same size.

What follows #

For a code that grows its mesh. The calibration transfers. A rebuild period measured on a quarter-size test problem is within four per cent of optimal on the full one across every setup cost swept, and the direction of the residual error is known: it rebuilds slightly too rarely, so the correction is to shorten the period rather than lengthen it. That is the same habit the essay on choosing a regularisation parameter on a smaller problem measures in another field, and it comes out the same way — the rule transfers, the bias has a sign, and the sign is worth knowing.

For anybody quoting a staleness penalty. Quote the ratio and say which member it was read at. A penalty of “four times” means the last member of a nineteen-member sequence on 64 unknowns and 2.39 times over the run; on 256 unknowns the same two figures are 3.24 and 2.09. All four numbers are true of the same experiment and they are the reason a single-number penalty is not portable.

For the reader of a convergence bound. None of this is predicted by the square root of the condition number. The bound that turns a conditioning into an iteration count is loose by an order of magnitude on a preconditioned matrix whose spectrum is two clusters rather than a spread, and the quantity measured here is a ratio of two such counts, in which the looseness partly cancels and partly does not. The counts are cheaper to measure than the bound is to trust.

For the multigrid comparison. A rate genuinely independent of the size of the problem exists in this collection and looks nothing like this. The V-cycle’s factor of ten a cycle is the same at fifteen points and at a hundred and twenty-seven, and the reason it is the same is that the method is built to make it so. Nothing built the reuse ratio to be flat, and it is not; it is merely the flattest thing available, which is a different and weaker property, and worth naming as such.

For the rule itself. A threshold on how far the matrix has moved is still the wrong rule for the reason the drift-landing essay gives, and nothing here rehabilitates it. What the grid sweep adds is that the decision built on top of a correct rule barely depends on the size of the problem, so a code that is choosing a preconditioner to move its conditioning on purpose has one fewer axis to worry about than it might have feared. The remaining axes — where the drift lands, what a rebuild costs, and whether the smoothing directions the factor encodes are still the operator’s stiff directions, which is what solving whole grid lines at once is about — are all independent of n as well.

And for the sequence field’s own accounting. Four assets are carried between members of a sequence, and the essay that names them gives each a shelf life. This measures one of the four across a range of sizes and finds that its shelf life, expressed as a ratio, is very nearly a property of the drift alone. Expressed as a count of iterations it is not, and the two sentences are about the same figure.