A factorisation kept past its date

A continuation solves the same problem two hundred times with a parameter moved slightly between each one. A time-stepping code does the same thing with time as the parameter. In both, the matrix at member t is nearly the matrix at member t − 1, and the expensive object in the room is a factorisation of it.

Reusing that factorisation is the oldest trick in the subject. Newton’s method with a frozen Jacobian is the chord method, it is in every textbook, and what every textbook says about it is that it converges linearly rather than quadratically. That is true and it is not the interesting part. The interesting part is that a factorisation has a shelf life: a number of members it is worth serving, past which it should be thrown away, and the number is not a property of the algorithm.

What is measured #

The family is a continuation: F_t(x) = Ax + λx³ − b_t, with the root of member t known exactly because b_t was built from it. Each member is warm-started from the previous member’s answer, which is what makes the whole thing worth doing, and solved by a chord iteration — the same triangular solves against the same stored factor, repeated until the residual is below 10⁻¹⁰.

The cost model is a count and not an estimate: a factorisation is n³/3 + n² multiplications and a chord step is 4n² — a residual evaluation and a pair of triangular solves. At n = 120 that makes a factorisation worth about 30 chord steps, which is the exchange rate the whole essay turns on and the one the problem that arrives again sets up.

The sawtooth #

The per-member cost is the shape worth having, because it says what staleness costs in the currency the iteration is actually spending.

At a drift of 0.01 a member with the factor rebuilt at every member, every member takes 4 chord steps, twenty times over. Rebuilt every four, the members take

4 5 6 7 · 4 5 6 7 · 4 5 6 7 · 4 5 6 7 · 4 5 6 7

which is the sawtooth: the member the factor was built for takes four steps and the member three later takes seven. Rebuilt every eight, the teeth are longer and steeper —

4 5 6 7 8 9 11 12 · 4 5 6 7 8 9 10 11 · 4 5 6 7

— and the last member under one factor costs three times what the first did.

Nothing here is a loss of accuracy. Every one of those members reaches the same tolerance and returns an answer at the same distance from a root that is known exactly. What ageing costs is steps, and steps are cheap, which is exactly why the trade is worth making.

Where the optimum is #

Summing the sawtooth against the factorisations gives the crossover. At a drift of 0.01 a member, over twenty members:

The optimum is every five members at 9.27 MFlop against 16.42 for refactorising every time — 44 per cent of the work saved, on a decision that is one integer in a configuration file.

And then the cliff. At a period of fifteen the sequence still converges, at 59 per cent more work than the optimum, which is a bad choice and an available one. At twenty it does not converge at all.

The cliff is not a gradual thing #

The refusal this essay carries is aimed at the most natural wrong reading of the table above, which is that keeping a factorisation too long buys work with accuracy.

It does not. Every period from 1 to 15 returns the same answer — the same distance from the known root, to the tolerance the iteration was asked for — and differs only in what it cost. At 20 the chord iteration’s contraction factor passes 1 and the iteration diverges: the residual grows, the run is cut off, and there is no answer of any quality at all.

That is a different shape of failure from everything else in this field. A loose forcing term costs work. A stale preconditioner costs iterations. A stale factorisation costs steps until it costs everything, and there is no warning between the last good period and the first bad one that anything was about to change.

The shelf life shortens with the drift #

The optimum is not a property of the method or of the matrix. It is a property of how fast the sequence is moving, and it moves the way it should:

At the fastest drift the optimum and the cliff are adjacent: refactorising at every member is the only fixed policy that works, and it is also the best one. At the slowest, one factor serves five members and the failure is four periods further out.

The practical difficulty is now visible. The right period depends on a quantity the code does not know, and getting it wrong in one direction wastes 77 per cent of the work while getting it wrong in the other produces no answer at all.

The rule that reads the ratio #

The chord iteration already computes the quantity that decides this, and does not use it.

At each step it evaluates the residual, so it has ‖Fₖ‖ and ‖Fₖ₋₁‖. Their ratio is the observed contraction factor of the iteration as it is actually running — not a bound, not an estimate from the matrix, the thing itself. A fresh factorisation gives a ratio around 0.05 on this problem; a factor several members old gives 0.3; a factor about to fail gives one close to 1.

So: refactorise the moment the observed ratio exceeds ρ*, and use nothing else.

At ρ* = 0.2 the rule costs 9.22 MFlop at a drift of 0.01 with four factorisations, against the best fixed period’s 9.27 with four. At 0.02 it costs 10.80 with six, against the best fixed period’s 12.14. At 0.05 it costs 13.26 with nine, against 16.85. At 0.10 — where every fixed period but one has fallen off the cliff — it costs 15.51 with thirteen factorisations, against 23.16 for the only fixed policy that works, a third less.

It never fails, and what it is worth against the best fixed period depends on the drift in a way worth setting out, because at one of the four stops it is worth less than nothing.

Across the four drifts the figure draws — 0.001, 0.0032, 0.01 and 0.032 a member — the rule costs 4.85, 7.46, 9.22 and 12.33 MFlop against a best fixed period of 4.85, 6.71, 9.27 and 14.50. So it ties at the slowest, loses by eleven per cent at 0.0032, wins by half a per cent at 0.01 and by fifteen per cent at 0.032.

That middle row is the useful one and it is not a defect of the rule. At a drift of 0.0032 the sequence’s members are nearly interchangeable: one factorisation serves about ten of them wherever it is built, so a fixed period of ten spends every factorisation to its last member and a rule watching the ratio refactorises a little early — twice over the run rather than the fixed policy’s twice, at a worse pair of places. The premium is what it costs to discover a number that was constant anyway.

Which is the essay’s own later sentence arriving as a measurement rather than as a summary: a rule is worth what the variation is worth. Where there is none it charges eleven per cent, where there is a lot it saves fifteen, and — the asymmetry that decides it — where the fixed policies fall off the cliff it is the only thing still running.

Why it wins where it wins #

The reason the rule does better as the drift gets faster is worth being explicit about, because it is not that it is cleverer there.

A fixed period is a claim that every factorisation is worth the same number of members. It is not: the drift is not uniform along the sequence, the nonlinearity means the Jacobian changes faster at some members than at others, and a factorisation built at an easy member genuinely lasts longer than one built at a hard member. A fixed period has to be short enough for the worst factorisation in the run, so it wastes work on all the others.

The rule spends each factorisation until it is used up. At the fastest drift, where the variation between members is largest, that is worth a third of the run; at the slowest, where every factorisation is worth about five members, it is worth almost nothing, and the two policies land within half a per cent of each other.

A rule is worth what the variation is worth, which is a sentence about when to bother rather than about what is optimal.

Two ways to be wrong, and they are not the same size #

The asymmetry in this decision is worth stating as a number, because it is what makes the rule worth having rather than merely elegant.

At a drift of 0.01 a member, being too eager — refactorising every member when every five would do — costs 16.42 MFlop against 9.27, which is 77 per cent more work for the same answer. Annoying, invisible, and survivable for years.

Being too patient — keeping a factor for twenty members when five was right — costs the run. Not an answer with fewer digits: no answer. The residual grows, the iteration is cut off, and whatever the outer code does with a member that failed to converge is now the behaviour of the program.

Those two are three periods apart at one drift rate and adjacent at another. A configuration file holding a number tuned on last month’s problem is therefore sitting somewhere on a line whose safe end and cliff have both moved since it was written, and nothing about a successful run reports how close to the edge it was.

The contraction rule removes the asymmetry rather than balancing it. It cannot be too patient, because the quantity it watches is exactly the one that says the iteration is in trouble, and it notices within a single step. It can be slightly too eager — ρ* = 0.2 is a choice — and being too eager is the cheap direction.

What the warm start is doing underneath #

There is a quantity that does not appear anywhere above and without which none of it works, which is worth making explicit because it is the reason a factorisation can be stale at all.

Each member is started from the previous member’s answer. The correction it needs is therefore of the size of the drift rather than of the size of the solution, and a chord iteration converges linearly with a factor governed by how far the frozen Jacobian is from the current one. Those two facts multiply: a small correction contracted by a factor near 0.05 reaches the tolerance in four steps, and the same factor applied to a cold start would need dozens.

That is also why the number here belongs to this problem rather than to the method: a sequence solved cold is a different measurement wearing the same words. So the shelf life measured here is not a property of the factorisation alone. It is a property of the factorisation and the warm start together, and a code that solves each member from scratch would find a much shorter one — the frozen Jacobian would have to carry the iteration all the way from nothing rather than across a gap the continuation already closed.

That is the sense in which this field’s four decisions are not independent of each other. Warm starting makes reuse worth having; reuse makes the per-member cost small enough that the drift rate becomes the binding constraint; and the drift rate is what decides the period. Change any one of the three and the arithmetic above has to be redone, which is the argument for measuring rather than inheriting a number from somebody else’s problem.

The rule has a constant too, and it cannot lose a run #

ρ* = 0.2 is a number somebody chose, and the previous section rather glides past that. It is worth sweeping, because the answer is the most interesting thing on this page: it explains why this free rule works when the one on preconditioner reuse does not.

Four thresholds, at the four drift rates. At a drift of 0.01 a member the rule costs 9.22 MFlop at ρ* = 0.2, 9.66 at 0.3, 11.49 at 0.5 and 15.12 at 0.7. At 0.02 it costs 10.80, 11.82, 14.21 and 17.55. At 0.05: 13.26, 14.11, 15.97, 19.87. At 0.10: 15.51, 16.29, 18.99 and 21.11.

Two things fall out of that grid and both are worth carrying.

No setting of the rule ever fails. Sixteen runs, four thresholds against four drift rates, and every one of them converges. Compare the fixed periods: at a drift of 0.10 the periods of 2, 3, 4, 5, 6, 8, 10, 15 and 20 all fall off the cliff, and only every member survives. Nine of ten fixed policies lose the run at that drift; none of four thresholds does.

That is not luck and it is not the threshold being well chosen. It is a bound the mathematics supplies. A chord iteration diverges exactly when its contraction factor passes 1, and the rule fires when the observed factor passes ρ*. So any ρ* below 1 necessarily fires before the cliff, and the run cannot be lost by setting it badly — only by setting it above 1, which is a setting that means “never refactorise” and is visibly not a rule.

The growth rule has no such ceiling. Its threshold is a ratio of iteration counts, and nothing in the problem says how large that ratio can get before the preconditioner is useless — a preconditioned solve that takes four times as many steps as a fresh one is slow, not broken. So there is no value that is safe by construction, and at γ = 3 that rule silently becomes the never-rebuild policy while still looking like a rule. The two rules read the same kind of quantity — a ratio the iteration already computed, dimensionless and scale-free — and only one of them reads a quantity with a known failure value in it.

And the constant matters least where the decision matters most. At the fastest drift, every one of the four thresholds beats the best fixed period: even ρ* = 0.7, which refactorises only six times, costs 21.11 MFlop against the 23.16 of the only fixed policy that works. At the slowest drift, where the sequence is gentle and a fixed period is a perfectly sensible thing to write down, ρ* = 0.5 and 0.7 both lose to it — 11.49 and 15.12 against 9.27.

So the honest summary of the rule is narrower than “it beats every constant” and more useful. It cannot lose a run at any setting; it costs work rather than answers when it is set loosely; and the setting stops mattering exactly as the problem gets hard enough for the setting to be difficult to choose. A fixed period has the opposite profile on all three counts, and the field’s other reuse decision has the opposite profile on the first one, which is the whole of why it is a harder decision.

What a threshold is really reading #

One more distinction, because the two rules are often described in the same breath and they are not the same idea.

The contraction ratio is a measurement of the iteration in progress. It says how fast this loop, right now, on this member, with this frozen factor, is shrinking its residual — and the failure it is guarding against is that number reaching 1, which is the same number. The instrument and the fault are the same quantity, so the instrument cannot be pointed at the wrong thing.

An iteration count is a measurement of an outcome. It says how much a solve cost, which is downstream of staleness, of the right-hand side, of where the previous iterate landed and of the stopping tolerance. Several things move it and only one of them is what the rule wants to know, which is why the growth rule is fooled by a sequence with no drift in it at all and why it rebuilds twice there.

That is a better statement of this field’s reading than “recompute rather than tune”. The rule wants a quantity whose failure value is known and which nothing else moves. The contraction ratio is such a quantity; an iteration count is not; a residual ratio in an inexact Newton iteration is. Where the field’s rules work, they work for that reason, and where one of them does not, it is because no such quantity was available and a proxy was used instead.

What is not measured here #

Two limits, both real.

The cost model is dense. A factorisation at n³/3 and a solve at 4n² is right for a dense Cholesky and wrong for everything a large code actually holds. The essay on what a rebuild is worth takes the exchange rate out of the model and makes it the axis, because it is the only thing that moves the answer.

The problem is symmetric positive definite, so there is no pivoting to reuse and no question of whether the factorisation is still valid — only of whether it is still good. The essay on a pivot order kept is the other case, and there the reuse can fail in a way that no number of extra steps repairs — the structure the ordering was chosen for is no longer the structure in front of it, which makes it a question about validity rather than about quality.