A warm start is degree zero

The problem that arrives again lists five things a sequence carries between its members and gives the fifth a paragraph of its own, because it is the one nobody argues about:

There is a fifth thing carried between members and it is so obviously right that it is worth saying why it belongs on the list: the previous answer, used as the starting point for the next member. It is free, it is never wrong, and it is the reason the other four decisions exist at all.

Free and never wrong, both true. Best available, which is what so obviously right implies, is not.

At a drift of 0.02 the warm start costs 160 inner steps over the run. The line through the last two answers costs 12. Same final accuracy — 1.6·10⁻⁹ against 1.5·10⁻⁹ — same factorisation schedule, same everything else, and a factor of thirteen in the work.

That bar is where the arithmetic here lands. The drifting case costs 86 per cent of solving every member from scratch, which is a seventeen per cent saving for the whole apparatus of reuse, and the field’s first essay calls it a poor advertisement. The measurements on this page come out of the same column and are much larger, because they are not competing with the factorisation’s cost at all — the factorisations are unchanged and it is the chord steps between them that fall by an order of magnitude.

That figure is worth a sentence beside everything above, because it is the case where the two economies part company. At six members the machinery of keeping a factorisation costs more than it saves: 100.4 per cent of the independent cost. The extrapolation has no such threshold — it saves on the first member it has two samples for, it costs nothing to set up, and it is as valuable on a six-member sweep as on a two-hundred-member one.

So the two carried objects amortise differently. A factorisation is an investment that pays back over members and can fail to pay back at all; a starting point is a saving on the very next solve. A code with a short sequence should extrapolate and not bother reusing, which is the opposite of the advice the field’s cost classification gives on its own.

Why nobody does it #

Worth a paragraph, because a factor of thirteen for three vector operations invites the question.

The construction is standard in continuation codes, where it is called a tangent predictor or a secant predictor and is a well-known part of the method. It is nearly absent everywhere else — in a time-stepping code the analogue is the integrator’s own predictor and is inside the method rather than in the linear algebra, and in a parameter sweep or a design study the members are usually handed to a solver one at a time through an interface that takes one starting vector.

That interface is the reason. A solver that accepts a starting point accepts one point, so a caller with a history has nowhere to put it and the extrapolation has to happen in the caller’s code — where the caller has to know that the previous answers are worth keeping, which is exactly what the field’s first essay says about all five carried objects. The difference is that the other four are properties of the matrix and this one is a property of the answers, so it does not even look like something a linear algebra library would offer.

What the extrapolation is #

A warm start says: the answer to member s + 1 is near the answer to member s, so start there. That is a polynomial in the parameter, of degree zero, fitted to one point.

The members lie along a path — x*(t) as t moves — and the answers to the previous members are samples of that path. So the obvious generalisation is to fit a polynomial of degree one to the last two samples and evaluate it at the new t, which for equal steps is

$$x_0 = 2x_s - x_{s-1}$$

and of degree two to the last three, which is $3x_s - 3x_{s-1} + x_{s-2}$.

Both need the previous answers, which a code already has or can keep for the price of one or two vectors. Both cost a handful of vector operations against an inner step that costs $4n^2$ — so at n = 120 the extrapolation is about 1/200th of one step of the thing it is saving thirteen of.

Degree one is worth a factor of thirteen #

The saving is not a margin.

At every drift where all three converge the line is between nine and fourteen times cheaper than the point, and the parabola is between four and seven times cheaper. The reason is geometric rather than numerical: the warm start begins a distance of one drift step away from the answer, and the linear extrapolation begins a distance of one curvature away — which on a smooth path is the square of the step rather than the step.

So the saving should grow as the steps get smaller, and it does not quite: 110/12 = 9.2 at a drift of 0.01 against 275/19 = 14.5 at 0.04. What limits it at the small end is that twelve steps over twenty members is barely more than half a step per member, and an iteration cannot take less than one step when it takes any.

That floor is worth naming because it is the only thing bounding the whole economy. Twenty members cannot cost fewer than twenty inner steps if every member needs its residual evaluated and corrected once, and the linear extrapolation is already at twelve — which means some members are being accepted without a single correction, their extrapolated starting point already inside the stopping tolerance. At that point the sequence has stopped being twenty solves and become twenty residual evaluations with occasional corrections, which is a different computation from the one the field’s cost classification prices, and the classification’s four bars have no column for it.

And degree two is worse than degree one #

The row that is not what a reader expects is the third column.

The parabola uses more information, fits the path better, and starts further from the answer than the line does: 26 steps against 12 at a drift of 0.02, and 38 against 19 at 0.04. Higher order is worse, at every drift drawn, by roughly a factor of two.

The cause is in the coefficients. The linear formula is $(2, -1)$ applied to the last two answers and the quadratic is $(3, -3, 1)$ applied to the last three. Their norms are $\sqrt{5} = 2.24$ and $\sqrt{19} = 4.36$, so the quadratic amplifies whatever error the stored answers carry by twice as much — and the stored answers are not exact. Each was accepted when its residual fell below the solve tolerance, so each carries an error at about that level — the floor the accuracy that is thrown away is about — and the extrapolation multiplies it.

The path’s curvature is what the quadratic buys and the stored answers’ error is what it pays, and on this family the second is larger. It is the same accounting cancellation takes the answer makes about a difference of nearly equal numbers: a formula whose coefficients alternate in sign and sum to one is a subtraction, and a subtraction’s relative error is the size of its terms over the size of its result. That predicts a regime where the quadratic wins: a tighter solve tolerance makes the stored answers better without changing the path, so there should be a tolerance below which degree two overtakes degree one. Nothing here finds it, and it is the obvious sweep.

The start and the factorisation are not the same purchase #

The slider on those figures changes how many members one factorisation serves, and the three curves move together without converging.

A fresher factorisation takes larger steps — it is a better approximation to the current Jacobian — so it forgives a poor starting point. A better starting point has less distance to travel. Both reduce the inner steps and neither substitutes for the other, which the numbers say directly: at a refactorisation every two members the warm start needs 122 steps and the line needs 9; at every eight it is 272 and 12. The factorisation’s freshness moves the first column by a factor of 2.2 and the second by 1.3.

That asymmetry is the useful part. The extrapolation is worth more when the factorisation is stale, which is the regime a code reusing factorisations is deliberately in — so the two economies are complementary rather than competing, and a code that has decided to keep a factorisation for eight members has the strongest possible reason to extrapolate its starting points.

Where the warm start stops converging and the line does not #

At a drift of 0.08, with one factorisation per four members, the warm start fails: the chord iteration hits its iteration cap on some member and the run stops. So does the quadratic. The linear extrapolation completes, at 23 inner steps, with a final error of 3.3·10⁻¹⁰.

That is a different kind of saving from a factor of thirteen. A chord iteration with a stale factorisation converges only if it starts inside a region whose size is set by how stale the factorisation is — the contraction the field’s first essay makes the whole of its reuse argument out of, and the starting point decides whether it is inside. The extrapolation is not merely cheaper there, it is the difference between a run and no run.

It also relocates the boundary the field’s other measurements are about. A factorisation kept past its date finds a cliff — a factor kept one period too long stops converging rather than losing accuracy — and the cliff’s position is quoted as a property of the drift and the factorisation. It is also a property of the starting point, and moving from degree zero to degree one moves it by at least one setting of the drift.

What a code should do #

The recommendation is short and it is the first one in this field that needs no measurement of the problem to apply — no drift rate, no rebuild period, no tolerance to pick. It is a change to two lines of a loop.

Keep the last two answers and extrapolate linearly. Two vectors of storage, three vector operations per member, and a factor of between nine and fourteen in the inner steps on every drift drawn.

Do not go to degree two without measuring, because on this family it is worse and the reason — amplified error in the stored answers — applies wherever the answers are stored at a solve tolerance rather than exactly.

And fall back to degree zero for the first member, which the routine here does automatically: an extrapolation of degree d needs d + 1 samples, so the first members of a run use whatever history exists. That is not a special case to write, it is one line, and it means the first member of a sequence is exactly the warm start the field’s first essay describes.

The refusals #

The claim worth breaking is the one the field’s first essay states and passes over: the previous answer is free, never wrong, and therefore the starting point to use. The first two halves are true. The assertion that no starting point beats it is fed the pair at a drift of 0.02 — 160 inner steps against 12, at the same final accuracy — and required to fail.

The second refusal covers the natural over-correction, which is that more history is better. Fed the quadratic at every drift, the claim that a higher-order extrapolation costs fewer steps than a lower one has to fail: 23 against 12, 26 against 12, 38 against 19.

And the third is the control that makes the comparison a comparison. Every starting point is fed the claim that it reached a worse answer than the others, and has to refuse at every drift — all three end within a factor of two of each other in forward error, so what is being measured is the cost of getting there rather than a trade against accuracy.

Where else an iteration’s history is thrown away #

The pattern — a computation that keeps one iterate when it has several — has two other instances in this collection and they are worth naming, because the repair is the same shape in all three.

A Krylov method keeps a whole subspace and uses it; that is what makes it a Krylov method, and restarting is a filter is precisely the decision to throw the history away and what it costs. A chord iteration in a sequence keeps one vector and discards the rest of the run, which is this page. And a stopping rule that reads the last two residuals rather than the last one — a tolerance that reads its own residual — is the same repair applied to a scalar: one extra remembered number, and a rule that beats every constant.

The common form is that a run produces a sequence and the code holds a point. In each case the repair costs storage that is negligible beside what is already held, and in each case the gain is a factor rather than a percentage. What differs is only how visible the discarded information is: a Krylov basis is obviously an object, a residual history is obviously a list, and a sequence’s previous answers look like finished work rather than like data.

What this does not measure #

Not unequal steps. The formulas above are the equally spaced ones. A batch visited in a sorted but unequally spaced order needs the general Lagrange coefficients, which are no harder and are not the same numbers — and whose norms, on which the degree-two penalty above depends, vary with the spacing.

Not a path with a corner. Every member here comes from a smooth family — unlike an interior-point method’s active set, where the identity of the binding constraints changes along the run and the answer’s path has a kink at every change, so the path x*(t) is smooth and a polynomial fits it. A sequence whose parameter crosses a bifurcation, or whose active set changes, has a path with a kink in it, and an extrapolation across a kink starts further away than the previous answer does. What a code should do about that is detect it, and the quantity that would — the residual of the extrapolated point against the residual of the warm start, both computable before the first inner step — is one evaluation each and is not measured here.

And not the outer loop’s own accuracy. All three starting points reach the same final error on every drift where they converge — 1.6·10⁻⁹, 1.5·10⁻⁹ and 1.7·10⁻⁹ at a drift of 0.02 — which is checked rather than assumed, because a cheaper start that arrived at a worse answer would be a different trade entirely.

Still open: the tolerance at which degree two wins #

The explanation above makes a prediction and the prediction is testable in one sweep.

The quadratic loses because it amplifies the stored answers’ error by 4.36 against the linear’s 2.24, and the stored answers carry an error at the solve tolerance. Tighten the tolerance and the amplified error falls while the path’s curvature — which is what the quadratic is fitting and the linear is missing — does not. So there should be a tolerance below which degree two overtakes degree one, and finding it would say which of the two effects the ordering of the columns above is really about.

The second open question is whether the extrapolation should be of the answer at all. What the iteration wants is a point where the residual is small, and the answer’s path and the residual’s are not the same object: an extrapolation that fitted the residuals and solved for where they vanish would be a secant method on the outer loop rather than a polynomial on its answers. Whether that is better, and whether it is even well defined when the members differ in more than a parameter, is unmeasured.

One line #

A warm start is a polynomial extrapolation of degree zero, degree one costs three vector operations and saves a factor of thirteen, and degree two is worse than degree one because it amplifies the error in the answers it is built from.