Numerical Linear Algebra
where the algebra stops being the arithmetic
When the problem arrives again

The degree the history chooses

A sequence of solves can start each member from the line through its last two answers or the parabola through its last three, and which is better depends on how much its path bends — which a code does not know. Over thirty runs of bend and tolerance, always taking the line costs 456 inner steps more than the better choice; always taking the parabola costs 33. A free rule reading the stored answers closes that to 11. A rule that evaluates the residual at both starts picks the better one on 29 runs of 30, and pays 135 steps for the evaluations.
20 min read 6 figures Measured, not assumedExact ground truthClaims that can fail

Worth reading first: The problem that arrives again · A warm start is degree zero · A parameter that counts steps.

A straight path has nothing for a parabola to fit drew a map. On a sequence of nonlinear solves whose roots move along a straight line, the line through the last two answers is the better starting point for the next member at every tolerance; bend the path by as little as a part in a hundred thousand and the parabola through the last three wins once the tolerance is tight enough. The map has a boundary and a code running a sequence does not know which side of it the sequence is on.

It does have a history. The previous answers are already stored — they have to be, to form either start — and each member’s inner iteration left a trail of corrections behind it. That essay closed by naming two rules that could read that history and choose. This one scores them.

Two rules that choose between the line and the parabola each member, scored against the better fixed choice on every run of the gridFor each of the thirty runs of the bend × tolerance grid, ordered by bend and then tolerance: the inner steps beyond the better of line and parabola for the worse of them, for a rule that takes the parabola when the gap between the two starts exceeds 2.1 times the previous member's last correction, and for a rule that evaluates the residual at both and keeps the smaller, whose extra residual per member is counted as a quarter of a step. The second-difference rule matches the better degree on 26 runs and is at most 5 steps behind; the residual rule matches on 29 and pays 4.5 steps for its evaluations on every run.010203040run, by bend then tolerancesteps beyond the better fixed degreestraightbend 10⁻⁵bend 10⁻⁴bend 0.001bend 0.01bend 0.1● second difference ■ residual at both ○ wrong fixed degreethirty runs: steps beyond the better degreesecond difference: runs matching the better degree, of 3026second difference: worst excess, steps5residual at both: runs matching the better degree, of 3029residual at both: extra residuals, in steps4.5wrong fixed degree: worst excess, steps35zero is the better degree, known in advanceeach group of five is one bend
Fig. 1 Thirty runs of twenty members — six bends of the path, five tolerances — and for each, the inner steps beyond the better of line and parabola. Open circles are what the wrong fixed choice would have cost; blue dots are a rule that reads only the stored answers; violet squares are a rule that evaluates the residual at both starts, with its evaluations counted.

Two rules and what each reads

The residual rule forms both starts, evaluates the nonlinear residual at each, and keeps the one with the smaller residual. It chooses by the very quantity the solve is stopped on, so it should be right whenever the two starts differ by more than a step’s worth. Its price is one residual evaluation per member beyond the one the iteration makes anyway: on this family a residual is a matrix–vector product and a cubic term, about n2n^2 multiply-adds, and an inner chord step is a residual plus two triangular solves, about 4n24n^2. So each choice costs a quarter of a step.

The free rule reads no residual. It forms both starts, measures the distance between them, and compares that distance with the size of the last correction the previous member took. If the gap is more than θ times the correction it takes the parabola, otherwise the line. The motivating arithmetic was the earlier essay’s: the gap between the two starts is the second difference of the stored answers, which contains the line’s truncation error; the last correction is a proxy for the error the stored answers carry; and the parabola’s larger amplification, 19\sqrt{19} against 5\sqrt{5}, should be worth paying once the truncation error exceeds about 19−5≈2.1\sqrt{19} - \sqrt{5} \approx 2.1 times that stored error. So θ = 2.1.

The first figure is both rules on every run at a drift of 0.02. The residual rule matches the better degree on 29 runs of 30 and is one step behind on the thirtieth — and every one of its violet squares sits four and a half steps above zero, which is eighteen extra residuals at a quarter of a step each. The free rule matches on 26 runs, and on the four it misses it is one to five steps behind. The wrong fixed choice, for comparison, costs up to 35 steps.

What the free rule is actually reading

The rule works better than its motivation deserves, and the reason is in the quantity it reads.

The quantity the free rule reads, member by member: the gap between the parabola's start and the line's, over the last correctionFor members four to twenty of four runs, the distance between the parabola's and the line's starting points divided by the size of the last inner correction the previous member took, on a logarithmic axis, with the threshold 2.1 = √19 − √5 drawn across. Medians: straight, 10⁻¹⁰ 1.3·10⁻⁸ (range 8.5·10⁻⁹ to 1); straight, 10⁻⁶ 1 (range 2·10⁻¹³ to 1); bent 10⁻⁴, 10⁻¹⁰ 38.3 (range 17 to 120); bent 10⁻², 10⁻⁶ 1 (range 1 to 1).357911131517192110⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹10²10³member of the sequencegap between the starts ÷ last correctionθ = 2.1: above it, take the parabolastraight, 10⁻¹⁰straight, 10⁻⁶bent 10⁻⁴, 10⁻¹⁰bent 10⁻², 10⁻⁶no residual is evaluatedthe gap is the second difference of the answers
Fig. 2 The gap between the two starts divided by the previous member’s last correction, member by member, for four runs, on a logarithmic axis. On the straight path the ratio is either about 10⁻⁸ or exactly one; on the path bent by 10⁻⁴ at a tight tolerance it sits between 17 and 120; on a strongly bent path at a loose tolerance it is exactly one at every member.

Several of those values are exactly one, which no estimate of a truncation error would produce. The algebra explains it. Suppose member s started from the line, 2xs−12x_{s-1} − xs−2x_{s-2}, and took corrections d1d_1, …, dkd_k. Then its answer is xsx_s = 2xs−12x_{s-1} − xs−2x_{s-2} + d1d_1 + … + dkd_k, and the second difference xsx_s − 2xs−12x_{s-1} + xs−2x_{s-2} — the gap the rule measures at member s + 1 — is exactly d1d_1 + … + dkd_k. The gap is the sum of the corrections the previous member needed. Divided by the last correction, the ratio is one if the member took one step, nearly zero if it took none, and large if it took several, each smaller than the one before.

So the free rule is not estimating curvature against stored error. It is asking whether the previous member, started from the line, needed more than one correction — the observation a guess worth two per cent makes from the other side, that a starting point is worth a count of iterations and not a share of them. On this family a chord step gains a little under a decade, so a member that needed three steps has corrections shrinking by about a sixth each, and the sum over the last is a few tens — which is the band the bent path sits in. The motivating threshold of 2.1 falls in the empty space between one step and several, and so, on this grid, does any threshold from just above one to sixteen.

The second-difference rule's total steps over the grid, against its thresholdTotal inner steps over the thirty runs of the bend × tolerance grid for the rule that takes the parabola when the gap between the two starts exceeds θ times the previous correction, against θ on a logarithmic axis: θ = 0.25: 1235, parabola chosen on 5 straight runs; θ = 0.5: 1217, parabola chosen on 5 straight runs; θ = 1: 1208, parabola chosen on 4 straight runs; θ = 2.1: 1224; θ = 4: 1224; θ = 8: 1224; θ = 16: 1224; θ = 64: 1297. Always the line totals 1669, always the parabola 1246, and the better degree for each run 1213.110¹11001200130014001500160017001800θ, the gap over the last correction beyond which the parabola is takeninner steps over thirty runs2420better degree, per runalways the linealways the parabolathirty runs, total inner stepsthe better degree, known for each run1213always the line1669always the parabola1246second difference, threshold 0.251235second difference, threshold 2.11224second difference, threshold 641297√19 − √5 ≈ 2.1 is the predicted thresholdno residual is evaluated
Fig. 3 Total inner steps over the thirty runs for the free rule at thresholds from a quarter to 64. Always the line is the upper dotted line and always the parabola the lower; the dashed line is the better degree chosen per run with the answers in hand.

The totals say the same. At every θ from 2.1 to 16 the rule’s total is 1,224 steps, identical: the ratios on these runs cluster at or below one and above that range, so moving the threshold inside it changes no choice. At θ = 64 it starts sending bent runs to the line and rises to 1,297. Below one it starts sending straight runs to the parabola — five of them at θ = 0.25 — and at θ = 1 it reaches 1,208, which is below the 1,213 of choosing the better degree per run with the answers known. A rule that decides member by member can beat an oracle that decides once per run, because the better degree can change within a run at the edge of the map.

The rule is still a good rule, and its derivation explains less of that than it claims. A rule that reads a step count is a stopping-test argument rather than a truncation argument, the same kind a rule that reads only its own probes makes from the samples it has already drawn: the evidence is something the computation produced for another purpose, and it is free because it was paid for already.

The mistakes are not the same size

The first figure’s open circles are the cost of the wrong fixed degree, and their heights are lopsided. On the straight path the wrong choice — the parabola — costs 4 to 6 steps. On the bent paths at tight tolerances the wrong choice — the line — costs 23 to 35.

Inner steps over thirty runs of the bend × tolerance grid, for five ways of choosing the starting point, at three driftsTotals over the thirty runs of bends 0 to 10⁻¹ and tolerances 10⁻⁶ to 10⁻¹⁴, with a residual evaluation counted as a quarter of an inner step. Drift 0.01: better degree 813, always the line 1211, always the parabola 839, second difference 849, residual at both 813 plus 135 for its evaluations. Drift 0.02: better degree 1213, always the line 1669, always the parabola 1246, second difference 1224, residual at both 1214 plus 135 for its evaluations. Drift 0.04: better degree 2170, always the line 2674, always the parabola 2221, second difference 2170, residual at both 2178 plus 135 for its evaluations.drift 0.018131211839849948drift 0.0212131669124612241349drift 0.0421702674222121702313the better degree, known per runalways the linealways the parabolasecond difference, θ = 2.1residual at both, evaluations counteda residual is n², a step 4n²totals over thirty runs of twenty members
Fig. 4 Inner steps over the thirty runs at drifts of 0.01, 0.02 and 0.04 for five strategies, with the residual rule’s evaluations counted at a quarter of a step each.

That asymmetry decides the whole comparison. At a drift of 0.02, choosing the better degree per run costs 1,213 steps. Always the line costs 1,669, which is 456 more. Always the parabola costs 1,246, which is 33 more. A code that knows nothing about its path and always takes the parabola gives up 33 steps in 1,246; one that always takes the line gives up 456. The free rule recovers 22 of the parabola’s 33. The residual rule recovers 32 of them and spends 135 on evaluations.

The pattern holds at the other two drifts, with one exception worth reporting. At 0.04 the line costs 504 more than the better choice and the parabola 51; the free rule matches the better choice exactly at 2,170; the residual rule is 8 behind and 143 behind with its evaluations. At 0.01 the line costs 398 more and the parabola 26 — and here the free rule, at 849, is worse than always the parabola at 839. At the smallest drift the stored answers are closest together, the line’s start is good enough on more members to take a single step, and a likely reading is that the rule sends those members to the line on runs where the parabola would have taken none; the measurement does not separate that from the rebuild schedule below.

Why the asymmetry: a start that is too close to need a step can only save the step it did not need, while a start that is too far costs a step for every decade it is short. The parabola’s penalty on a straight path is its twice-amplified stored error, a factor of about two in distance, which costs at most a step here and there. The line’s penalty on a bent path is a fixed floor that the tolerance keeps asking to go below, which costs a step per member per decade. One mistake is bounded and the other grows with the accuracy asked for.

Where the free rule misses

Inner steps over twenty members from three starting points, against the solve tolerance — a path bent by 10⁻⁵Twenty members of a drifting nonlinear sequence of 120 unknowns, one factorisation kept for four members, each started from the previous answer, from the line through the last two answers, or from the parabola through the last three; the roots lie on a line bent by 10⁻⁵·sin 3t along a second direction. The total inner steps against the relative residual tolerance from 10⁻⁶ to 10⁻¹⁴: 10⁻⁶: 62, 12, 17; 10⁻⁷: 87, 14, 18; 10⁻⁸: 113, 23, 18; 10⁻⁹: 135, 24, 23; 10⁻¹⁰: 160, 25, 25; 10⁻¹¹: 184, 39, 26; 10⁻¹²: 211, 53, 30; 10⁻¹³: 238, 72, 44; 10⁻¹⁴: 261, 90, 60.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶050100150200250relative residual tolerance of every solveinner steps over twenty membersprevious answerline, last twoparabola, last threea path bent by 10⁻⁵, twenty members, drift 0.02tolerance 10⁻⁶: previous answer62tolerance 10⁻⁶: line12tolerance 10⁻⁶: parabola17tolerance 10⁻¹⁰: previous answer160tolerance 10⁻¹⁰: line25tolerance 10⁻¹⁰: parabola25tolerance 10⁻¹⁴: previous answer261tolerance 10⁻¹⁴: line90tolerance 10⁻¹⁴: parabola60tighter to the lefteach point is a whole run of twenty
Fig. 5 A path bent by 10⁻⁵, the gentlest bend on the map. The line leads at 10⁻⁶ and 10⁻⁷, the parabola at 10⁻⁸ and 10⁻⁹, and they tie at 10⁻¹⁰ — 12 against 17, 23 against 18, 25 against 25 — before the parabola pulls away to 60 against 90.

The runs the free rule gets wrong at 0.02 are on the edges of the map, and this bend holds two of them. At 10⁻⁸ the parabola needs 18 steps and the line 23, but the line’s start is still good enough that most members take one correction, the ratio reads one, and the rule keeps the line. The truncation floor is there — the parabola’s five-step lead says so — but it has not yet made any single member take a second step. The rule reads effects, and a small effect spread thinly across members is invisible to a rule that looks at one member at a time.

That is the regime in which reading the residual earns its keep. The residual at the two starts differs even when both starts need one correction, so the residual rule picks the parabola there and gets the five steps. It is simply that five steps is less than the four and a half it pays on every run.

The same trail, read by two rules

The free rule is not the only reader of the previous member’s corrections. The factorisation schedule is another. A factorisation kept past its date found that rebuilding when the observed contraction between successive corrections degrades beats every fixed rebuild period, and that rule reads the same sequence of correction sizes the free rule sums.

The two readings can be confused with each other. A member that takes several corrections does so either because it was started far from its root or because the factorisation it is using has aged and each correction gains less. The free rule attributes every extra correction to the start and reaches for the parabola; a rebuild rule attributes a slow contraction to the factorisation and rebuilds. On the runs here the factorisation is rebuilt every four members on a fixed schedule, so the fourth member of each block works with the oldest factorisation, and the ratio the free rule reads can be inflated there for reasons that have nothing to do with the path.

That this does not show up as wrong choices on the straight path is because a straight path’s line start is so close that even an old factorisation finishes in one correction. It is a plausible contributor to the misses at the edges of the map, where a member’s step count is balanced between one and two, and this measurement does not separate the two causes. It also says something about combining the rules: a sequence that runs both has two controllers reading one signal, and whether they help each other or fight is a question the order of a batch makes sharper — the order a batch arrives in showed that shuffling a sequence multiplies its rebuilds, and a shuffled path is a bent one.

What a residual has to cost

The residual rule’s verdict depends entirely on one ratio: what a residual evaluation costs against an inner step. On a dense chord iteration that ratio is a quarter. It is not a quarter everywhere.

What choosing by residual costs, against the price of one residual evaluation measured in inner stepsAt drift 0.02 over the thirty runs, the residual rule takes 1214 inner steps and makes 540 extra residual evaluations. Its total in step-equivalents against the price of a residual as a fraction of a step, from 10⁻³ to 1 on a logarithmic axis, beside always the parabola at 1246, the second-difference rule at 1224 and the better degree per run at 1213. It beats the parabola below 0.059 of a step a residual and the second-difference rule below 0.019; on a dense chord step a residual is a quarter.10⁻³10⁻²10⁻¹11150125013501450155016501750price of one residual evaluation, in inner stepsstep-equivalents over thirty runsdense chord step: ¼residual at bothalways the parabolasecond differencebetter degree, per rundrift 0.02, thirty runsresidual at both, evaluations free1214residual evaluations it makes540break-even against always the parabola, steps a residual0.059break-even against the second difference0.019cheap residual, expensive step: the rule paysa preconditioned iterative step is many residuals
Fig. 6 The residual rule’s total over thirty runs at drift 0.02, in step-equivalents, against the price of one residual evaluation as a fraction of an inner step. The curve crosses always the parabola at 0.059 and the free rule at 0.019; the faint vertical line is a quarter, the dense chord step.

The rule beats always the parabola only if a residual costs less than about a seventeenth of a step, and beats the free rule only below about a fiftieth. On a dense chord iteration neither holds. But the inner step here is cheap because a factorisation has been paid for in advance. On a problem solved with a preconditioned Krylov method, an inner step is many matrix–vector products plus a preconditioner application, and a residual is one product; a ratio of a fiftieth is an ordinary inner iteration of a few dozen products. There the residual rule’s accuracy is worth having, and its 29 of 30 is the number to quote.

So the choice between the two rules is not about which is smarter. It is the same accounting a warm start is degree zero made about the extrapolation itself — a handful of vector operations against the thing they save — pushed one level further: what the evidence for choosing costs against what choosing saves. It is also the question a stopping test is a race asks of any test that has to be computed before it can be passed: a check is part of the cost of the thing it checks.

What a code should do

Three recommendations, in the order the measurements support them.

Keep three answers and extrapolate with the parabola if nothing is known about the path. On this grid it costs between 26 and 51 steps over thirty runs more than knowing the better degree, against 398 to 504 for the line, and it needs no rule at all. The one thing that can make it the wrong default is a drift so large that the parabola’s start fails to converge where the line’s does, and the earlier measurement found drifts at which the parabola’s start and the previous answer both stopped converging while the line’s did not.

Add the free rule if a few per cent matters. It costs a vector subtraction a member and recovers two thirds to all of what the parabola gives up at drifts of 0.02 and 0.04, with the understanding that what it reads is how many corrections the previous member needed, and that its threshold is anything comfortably between one and ten.

Use the residual rule only where a residual is much cheaper than an inner step. On a dense factorised chord iteration it loses to both; on an iterative inner solve it is the most reliable of the three.

What this rests on

The family of the earlier essay: 120 unknowns, a condition number of ten thousand, a cubic term; paths bent by c·sin 3t along a second random direction for c = 0 and 10⁻⁵ to 10⁻¹; tolerances 10⁻⁶ to 10⁻¹⁴; twenty members from t = 0.4 with a factorisation rebuilt every four. Drifts of 0.01, 0.02 and 0.04; at 0.08 the chord iteration with this rebuild schedule fails on every run and nothing can be scored. Costs are counted in inner steps with a residual at a quarter of one, which is exact for the dense arithmetic here and an assumption for anything else; the factorisations, which are the same for every strategy, are left out of every total.

The claim that has to fail

The claim is the natural one after the first figure: that a rule right on 29 runs of 30 pays for itself. At a drift of 0.02 it needs 1,214 inner steps and makes 540 extra residual evaluations, 135 steps’ worth on a dense chord iteration, for 1,349 against always the parabola’s 1,246. The refusal is fed the claim that the rule’s total is no larger and fails.

Still open: more than three answers, a path whose bend changes, and the two controllers together

Higher degrees, and fits rather than interpolants. The parabola is the last interpolant worth trying on this family: a cubic’s coefficients (4, −6, 4, −1) have norm 69≈8.3\sqrt{69} \approx 8.3, so it would need a third derivative the stored error cannot hide. A least-squares fit of a line or a parabola to four or five stored answers trades the other way — smaller amplification for a bias — and which of the two the asymmetry above favours is unmeasured.

A path whose bend varies along the run. Every path here has one bend for its whole length. A continuation through a turning point, or a sweep that crosses from a linear regime into a nonlinear one, would put the map’s boundary inside a single run, which is where a member-by-member rule should beat any fixed degree by more than the handful of steps it does here — and where the free rule’s blindness to thinly spread effects would matter most.

The degree rule and the rebuild rule on one sequence. Both read the previous member’s corrections, one to choose a start and one to decide a factorisation’s age. Running them together, on a path whose members arrive out of order, would say whether a correction count can be attributed to the right cause — two of the five things the problem that arrives again listed as carried between members, never yet measured as one decision.

Where this goes next

10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶050100150200250relative residual tolerance of every solveinner steps over twenty membersprevious answerline, last twoparabola, last threea straight path, twenty members, drift 0.02tolerance 10⁻⁶: previous answer62tolerance 10⁻⁶: line11tolerance 10⁻⁶: parabola17tolerance 10⁻¹⁰: previous answer160tolerance 10⁻¹⁰: line12tolerance 10⁻¹⁰: parabola14tolerance 10⁻¹⁴: previous answer261tolerance 10⁻¹⁴: line17tolerance 10⁻¹⁴: parabola23tighter to the lefteach point is a whole run of twenty A straight path has nothing for a parabola to fit The line through the last two answers beat the parabola through the last three on a drifting sequence, and the reason offered was that the parabola amplifies the stored answers' error. Tightening the solve tolerance from 10⁻⁶ to 10⁻¹⁴ should have reversed that, and it does not: the line needs 7 to 18 inner steps over twenty members at every tolerance and the parabola 14 to 23. The sequence's roots move along a straight line, so the line is exact and there is nothing else to fit. Bend the path by a part in ten thousand and the parabola wins below 10⁻⁹, by 105 steps to 75 at 10⁻¹⁴. 10⁻²10⁻¹10¹10²drift between consecutive membersinner steps over the whole runthe previous answer — a warm startthe parabola through the last threethe line through the last twodegree zero is a choicemembers per factorisation4warm, at drift 0.02160linear, at 0.0212quadratic, at 0.0226the factor13drifts where warm fails2one more term in the extrapolationand a factor of thirteen A warm start is degree zero The previous answer used as the next member's starting point costs 160 inner steps over twenty members. The line through the last two answers costs 12 — a factor of thirteen, for three vector operations and no extra storage. The parabola through the last three costs 26, which is worse than the line and better than the point. 40 drawsproducts at target 0.01696deflated277draws inside the target0.810⁻²10⁻¹10⁻²10⁻¹target standard errorrelative error reachedworst draw, no deflationmedian error, no deflationmedian error, deflatedthe grey diagonal is a calibrated rulethe medians are on it and the worst draws are not A rule that reads only its own probes A trace estimator is a mean of independent samples, so its own standard error is estimable from the samples and a stopping rule needs nothing the estimator does not already have. Over forty draws it is calibrated in the middle and not at the edge: at a target relative standard error of 1% the median error reached is 5.3·10⁻³ and the worst of forty is 2.9·10⁻² — three times the target. And the cost of the target is the estimator's own square root: tightening it from 3% to 1% takes the median probe count from 75 to 696.

What links here

Computed from the collection, not written here: the essays that point at this one.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Cholesky factorisationExact ground truthExtrapolationFlop countNewton iterationStopping criterionWarm start