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

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⁻¹⁴.
21 min read 6 figures Measured, not assumedExact ground truthWhose fault is it

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

A warm start is degree zero measured three starting points for the next member of a drifting sequence of nonlinear solves. The previous answer cost 160 inner steps over twenty members; the line through the last two answers cost 12; the parabola through the last three cost 26. It explained the third number by the parabola’s coefficients. The formula 3xs3x_s − 3xs−13x_{s-1} + xs−2x_{s-2} has a coefficient norm of 19≈4.36\sqrt{19} \approx 4.36 against the line’s 5≈2.24\sqrt{5} \approx 2.24, every stored answer carries an error at about the solve tolerance, and so the parabola doubles whatever error it is built from.

That explanation made a prediction, and the essay said so in its last section. The error the stored answers carry falls with the solve tolerance; the curvature of the path, which the parabola fits and the line misses, does not. So somewhere below the tolerance measured the parabola should overtake the line.

It does not, at any tolerance a double can reach.

Inner steps over twenty members from three starting points, against the solve tolerance — a straight pathTwenty 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 straight line in the parameter. The total inner steps against the relative residual tolerance from 10⁻⁶ to 10⁻¹⁴: 10⁻⁶: 62, 11, 17; 10⁻⁷: 87, 7, 16; 10⁻⁸: 113, 12, 16; 10⁻⁹: 135, 10, 14; 10⁻¹⁰: 160, 12, 14; 10⁻¹¹: 184, 17, 21; 10⁻¹²: 211, 17, 23; 10⁻¹³: 238, 18, 23; 10⁻¹⁴: 261, 17, 23.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
Fig. 1 Twenty members, one factorisation kept for four of them, drift 0.02, three starting points, against the relative residual tolerance each solve is stopped at. The previous answer’s cost climbs by about twenty-five steps a decade; the line and the parabola lie flat along the bottom, and the parabola is above the line at every tolerance.

The prediction, and what happened to it

At a tolerance of 10⁻⁶ the three starts cost 62, 11 and 17 inner steps. At 10⁻¹⁰, 160, 12 and 14. At 10⁻¹⁴, 261, 17 and 23. The previous answer pays for every decade of tolerance — each digit of accuracy has to be earned from the same distant start — and the two extrapolations barely notice the tolerance at all. Across eight decades the line needs between 7 and 18 steps over twenty members and the parabola between 14 and 23. The gap between them narrows to two steps near 10⁻¹⁰ and opens again to six.

So the prediction fails, and the interesting question is why the flat curves are flat. Twelve inner steps over twenty members is fewer than one step a member. A member that needs no correction at all has been handed a start already inside its tolerance, and that means the start is not near the next root in the sense of a smooth path’s curvature; it is at the next root to within the accuracy the solve asks for.

Where each start actually lands

The step count is a logarithm of a distance — the point a guess worth two per cent made about a better starting guess buying a constant handful of iterations rather than a share — so the distance is the thing to measure. Every member of this family has a known root, which makes the distance from each start to it exact.

How far each extrapolated start lies from the next root, against the solve tolerance — a straight pathFor the same twenty-member runs, the median over members four to twenty of the relative distance between the starting point and the member's exact root, against the solve tolerance, on logarithmic axes, with the tolerance itself drawn as a line. 10⁻⁶: previous 0.0312, line 1.07·10⁻⁴, parabola 1.81·10⁻⁴; 10⁻⁷: previous 0.0312, line 6.55·10⁻⁶, parabola 1.69·10⁻⁵; 10⁻⁸: previous 0.0313, line 9.19·10⁻⁷, parabola 1.58·10⁻⁶; 10⁻⁹: previous 0.0312, line 7.92·10⁻⁸, parabola 1.09·10⁻⁷; 10⁻¹⁰: previous 0.0312, line 9.29·10⁻⁹, parabola 1.12·10⁻⁸; 10⁻¹¹: previous 0.0313, line 9.45·10⁻¹⁰, parabola 1.51·10⁻⁹; 10⁻¹²: previous 0.0313, line 1.11·10⁻¹⁰, parabola 1.33·10⁻¹⁰; 10⁻¹³: previous 0.0312, line 1.1·10⁻¹¹, parabola 2.14·10⁻¹¹; 10⁻¹⁴: previous 0.0313, line 9.22·10⁻¹³, parabola 1.78·10⁻¹².10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹relative residual tolerance of every solvemedian distance of the start from the rootprevious answerline, last twoparabola, last threethe tolerancea straight path: median start distancetolerance 10⁻⁶: line1.1·10⁻⁴tolerance 10⁻⁶: parabola1.8·10⁻⁴tolerance 10⁻¹⁰: line9.3·10⁻⁹tolerance 10⁻¹⁰: parabola1.1·10⁻⁸tolerance 10⁻¹⁴: line9.2·10⁻¹³tolerance 10⁻¹⁴: parabola1.8·10⁻¹²a start that follows the dotted line is limited by the stored answersa flat one by the path
Fig. 2 The median distance of each start from its member’s root, relative to the root, against the tolerance on logarithmic axes. The previous answer sits at 3·10⁻² whatever the tolerance; the line and the parabola fall parallel to the dotted tolerance line, a couple of decades above it, all the way down.

The previous answer starts 3.1 per cent from the next root at every tolerance, because that is how far the root moves in one drift step. The line starts 1.1·10⁻⁴ away at a tolerance of 10⁻⁶, 9.3·10⁻⁹ at 10⁻¹⁰ and 9.2·10⁻¹³ at 10⁻¹⁴ — about a hundred times the tolerance, all the way down. The parabola starts 1.2 to 2.6 times further than the line at every tolerance.

A start that tracks the tolerance is limited by nothing but the stored answers. If the path had curvature the line would miss it, and the miss would not shrink as the tolerance tightened; the line’s curve would flatten out at that miss. It never flattens. So the line is not missing the path by anything measurable. It is on it.

That is because the path is a straight line. Each member of this family is built so that its root is t times a fixed vector, with t the parameter that drifts. Stored answers at t, t + 0.02 and t + 0.04 are three points on a line through the origin, and the line through any two of them passes through the third exactly. The parabola’s extra coefficient fits a second derivative that is identically zero, and all it adds is a larger multiple of the stored error.

So the explanation the earlier essay gave was correct in its mechanism and incomplete in what it left out. The parabola does amplify stored error by about twice as much — its coefficients alternate in sign and sum to one, which is the shape cancellation takes the answer prices as a subtraction of nearly equal things. What the line is supposed to pay in return — the curvature it cannot represent — is zero on this family, and a trade in which one side pays nothing cannot be reversed by making the other side’s price smaller.

Why a hundred times the tolerance rather than the tolerance itself: the tolerance is on the relative residual, and the distance is a relative error in the answer, which can be larger by up to the condition number of the Jacobian. At a condition number of ten thousand, a factor of a hundred is the ordinary gap between the two, and it is the reason a start a hundred tolerances away in error can pass the residual test without a single step.

What a decade of tolerance costs from each start

The flat curves and the steep one are the same arithmetic read from different starting distances. The previous answer’s cost rises from 62 steps at 10⁻⁶ to 261 at 10⁻¹⁴: 199 steps for eight decades over twenty members, or about one and a quarter steps a member for each decade asked for. So each chord step with a factorisation up to four members old gains a little under a decade — a contraction of about a sixth a step — and a start 3 per cent from the root needs about as many steps as it has decades to cover, plus one.

An extrapolated start has almost no decades to cover. It lies a hundred tolerances from the root in error, which is inside the tolerance in residual more often than not, so most members are accepted on their first residual evaluation and the rest need one correction. Tighten the tolerance and the stored answers tighten with it, so the start is still a hundred tolerances away and the count does not move. That is what a flat curve on the first figure means: the cost of a digit has been paid by the previous member, which had to reach it anyway, and passed on for the price of a subtraction.

It also says what the accuracy that is thrown away looks like from the other side. Every accepted answer carries accuracy the next member can use only if its start is built from it; the previous answer used alone throws away the direction of travel, and the step count pays for that at a steady rate per decade.

A path that bends

To give the parabola something to fit, the roots can be moved off the line. Each member’s root becomes t times the old vector plus c·sin(3t) times a second random vector. At c = 0 this is the family already measured. For c > 0 the path has a second derivative of size about 9c and a third of about 27c along the second direction, and nothing else about the problem changes: the same matrix, the same cubic term, the same drift and the same factorisation schedule, the rebuild every four members that a factorisation kept past its date found cheaper than rebuilding every member.

The line now misses the path by its truncation term — about cω2dt2c\omega^2 dt^2, with ω = 3 and a drift of 0.02 — and the parabola by cω3dt3c\omega^3 dt^3, a factor of ω dt=0.06\omega\,dt = 0.06 smaller. Each adds its amplified stored error on top.

How far each extrapolated start lies from the next root, against the solve tolerance — a path bent by 0.001For the same twenty-member runs, the median over members four to twenty of the relative distance between the starting point and the member's exact root, against the solve tolerance, on logarithmic axes, with the tolerance itself drawn as a line. 10⁻⁶: previous 0.0312, line 5.09·10⁻⁶, parabola 2.32·10⁻⁴; 10⁻⁷: previous 0.0313, line 5.09·10⁻⁶, parabola 5.74·10⁻⁶; 10⁻⁸: previous 0.0313, line 5.09·10⁻⁶, parabola 2.22·10⁻⁷; 10⁻⁹: previous 0.0313, line 5.21·10⁻⁶, parabola 1.22·10⁻⁷; 10⁻¹⁰: previous 0.0313, line 5.19·10⁻⁶, parabola 9.4·10⁻⁸; 10⁻¹¹: previous 0.0313, line 5.2·10⁻⁶, parabola 9.63·10⁻⁸; 10⁻¹²: previous 0.0313, line 5.19·10⁻⁶, parabola 9.51·10⁻⁸; 10⁻¹³: previous 0.0313, line 5.19·10⁻⁶, parabola 9.49·10⁻⁸; 10⁻¹⁴: previous 0.0313, line 5.19·10⁻⁶, parabola 9.5·10⁻⁸.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻⁸10⁻⁶10⁻⁴10⁻²1relative residual tolerance of every solvemedian distance of the start from the rootprevious answerline, last twoparabola, last threethe tolerancea path bent by 0.001: median start distancetolerance 10⁻⁶: line5.1·10⁻⁶tolerance 10⁻⁶: parabola2.3·10⁻⁴tolerance 10⁻¹⁰: line5.2·10⁻⁶tolerance 10⁻¹⁰: parabola9.4·10⁻⁸tolerance 10⁻¹⁴: line5.2·10⁻⁶tolerance 10⁻¹⁴: parabola9.5·10⁻⁸a start that follows the dotted line is limited by the stored answersa flat one by the path
Fig. 3 The same measurement on a path bent by c = 10⁻³. The line’s start is already at its floor of 5.1·10⁻⁶ at a tolerance of 10⁻⁶ and never moves; the parabola’s tracks the tolerance down to 10⁻⁸ and stops at 9.5·10⁻⁸.

Both floors are where the truncation terms put them. The line’s floor at 5.2·10⁻⁶ against a leading term c·ω2\omega^2·dt² of 3.6·10⁻⁶; the parabola’s at 9.5·10⁻⁸ against 2.2·10⁻⁷. The ratio between the two floors is 55 against the 17 that 1/(ωdt) gives, and the difference is the sine and cosine that weight the second and third derivatives along this stretch of the path, which one bend at one frequency cannot separate. And the picture has the shape the earlier essay expected: at loose tolerances the stored error dominates and the line is ahead, and once the tolerance is small enough that the line’s floor is the larger term, the parabola starts closer.

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, 13, 17; 10⁻⁷: 87, 22, 18; 10⁻⁸: 113, 23, 22; 10⁻⁹: 135, 24, 24; 10⁻¹⁰: 160, 39, 26; 10⁻¹¹: 184, 52, 30; 10⁻¹²: 211, 71, 43; 10⁻¹³: 238, 89, 59; 10⁻¹⁴: 261, 105, 75.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⁻⁶: line13tolerance 10⁻⁶: parabola17tolerance 10⁻¹⁰: previous answer160tolerance 10⁻¹⁰: line39tolerance 10⁻¹⁰: parabola26tolerance 10⁻¹⁴: previous answer261tolerance 10⁻¹⁴: line105tolerance 10⁻¹⁴: parabola75tighter to the lefteach point is a whole run of twenty
Fig. 4 Inner steps on a path bent by c = 10⁻⁴. The previous answer is unchanged. The line and the parabola stay within four steps of each other down to 10⁻⁹; below it the line climbs by about sixteen steps a decade and the parabola by about twelve, ending at 105 and 75.

On a path bent by a part in ten thousand the two extrapolations stay within four steps of each other down to a tolerance of 10⁻⁹, and the lead changes hands twice on the way. Below that the line’s cost starts climbing — every decade past its floor is a decade it has to earn with inner steps — and at 10⁻¹⁴ it needs 105 against the parabola’s 75. The parabola climbs too, because its own floor is only 55 times lower, but it starts climbing later.

This is the reversal the earlier essay predicted, on a path that has a second derivative. The prediction was right about the tolerance and wrong about the family it was made on.

The map of which one wins

Whether the line or the parabola through the stored answers starts a drifting sequence better, over the bend of its path and the solve toleranceTwenty-member runs at drift 0.02 on paths bent by c·sin 3t, for c from 0 to 10⁻¹ and tolerances from 10⁻⁶ to 10⁻¹⁴. Each cell gives the inner steps from the line and from the parabola, shaded by which is fewer. c = 0: 11/17, 12/16, 12/14, 17/23, 17/23; c = 10⁻⁵: 12/17, 23/18, 25/25, 53/30, 90/60; c = 10⁻⁴: 13/17, 23/22, 39/26, 71/43, 105/75; c = 0.001: 21/17, 23/23, 52/29, 88/58, 125/93; c = 0.01: 21/20, 37/24, 71/42, 107/73, 144/109; c = 0.1: 21/21, 50/27, 93/58, 125/93, 168/133.inner steps, line / parabolatol 10⁻⁶tol 10⁻⁸tol 10⁻¹⁰tol 10⁻¹²tol 10⁻¹⁴straight11/1712/1612/1417/2317/23bend 10⁻⁵12/1723/1825/2553/3090/60bend 10⁻⁴13/1723/2239/2671/43105/75bend 0.00121/1723/2352/2988/58125/93bend 0.0121/2037/2471/42107/73144/109bend 0.121/2150/2793/58125/93168/133the line needs fewer steps (left number)the parabola needs fewer (right)tiedtwenty members, drift 0.02, rebuilt every fourbend: c in c·sin 3t
Fig. 5 Inner steps for the line (left) and the parabola (right) on every combination of six bends and five tolerances. The winner of each cell is in bold and its cell shaded.

The top row is the straight path and the line wins every cell of it: 11 against 17, 12 against 16, 12 against 14, 17 against 23 twice. Every other row is won by the parabola from some tolerance downward, and the tolerance at which it starts winning moves with the bend. At c = 10⁻⁵ the parabola is five steps ahead at 10⁻⁸, the two tie at 10⁻¹⁰, and the parabola wins by 23 and 30 below; at 10⁻⁴ they are a step apart at 10⁻⁸; at 10⁻² and 10⁻¹ the parabola is already ahead at 10⁻⁸ by 13 and 23 steps.

The boundary roughly follows the floor. The line’s floor on this family is about 5·10⁻³ times the bend, and the parabola overtakes it once the tolerance is a hundred to a few hundred times smaller than that floor — which is where the line’s start, a hundred tolerances from the root through its stored error, stops being limited by the stored error and starts being limited by the path. At 10⁻⁵ that is a tolerance of about 10⁻¹⁰, at 10⁻³ about 10⁻⁸, and both are where the map changes colour.

At the loosest tolerance the counts on the bent rows are within four steps of one another and the winner changes from row to row, which is the regime in which neither start is limited by anything but the stored error and a step or two is the noise of where a member happens to cross its tolerance.

The winning margins on the bent rows are not small. At 10⁻¹² the parabola saves 23, 28, 30, 34 and 32 steps across the five bends, between a quarter and two fifths of the line’s cost. The earlier essay’s factor of thirteen came from the line against the previous answer; this is a further third off the line, on any path that curves enough for a tight tolerance to see it.

Inner steps over twenty members from three starting points, against the solve tolerance — a path bent by 0.01Twenty 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 0.01·sin 3t along a second direction. The total inner steps against the relative residual tolerance from 10⁻⁶ to 10⁻¹⁴: 10⁻⁶: 63, 21, 20; 10⁻⁷: 87, 22, 22; 10⁻⁸: 113, 37, 24; 10⁻⁹: 135, 51, 28; 10⁻¹⁰: 160, 71, 42; 10⁻¹¹: 185, 89, 57; 10⁻¹²: 212, 107, 73; 10⁻¹³: 238, 124, 92; 10⁻¹⁴: 261, 144, 109.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 0.01, twenty members, drift 0.02tolerance 10⁻⁶: previous answer63tolerance 10⁻⁶: line21tolerance 10⁻⁶: parabola20tolerance 10⁻¹⁰: previous answer160tolerance 10⁻¹⁰: line71tolerance 10⁻¹⁰: parabola42tolerance 10⁻¹⁴: previous answer261tolerance 10⁻¹⁴: line144tolerance 10⁻¹⁴: parabola109tighter to the lefteach point is a whole run of twenty
Fig. 6 A path bent by c = 10⁻², a hundred times more than the earlier one. The line and the parabola agree at 10⁻⁶ and 10⁻⁷; from 10⁻⁸ the line climbs almost as steeply as the previous answer, and the parabola follows a decade later, 144 against 109 at 10⁻¹⁴.

On this bend the line’s floor is reached before the first tolerance on the axis is tightened much, and from 10⁻⁸ down it pays about eighteen steps a decade against the previous answer’s twenty-five. The line has become a start of fixed distance, like the previous answer but closer, and the parabola is the only one of the three still being carried by the stored answers down to 10⁻⁹.

How much bend a real sequence has

A straight path is not a contrivance of this family alone. Any sequence whose parameter enters the problem linearly and whose solution depends on it linearly has one: a right-hand side that ramps, a load that scales, a source term swept in amplitude on a linear problem. Continuation on such a problem is the case the line was made for, and it gains nothing from a higher degree.

Most sequences are not like that. A parameter that enters a nonlinear problem bends the path through the nonlinearity, a time-stepping sequence follows whatever the dynamics do, and a design sweep moves through a response surface with no reason to be flat. Even the order in which a batch is visited changes the bend a sequence sees: the order a batch arrives in sorted members by their parameter, and a sorted path is the smoothest the parameter allows, so a shuffled one bends more between consecutive members than any row of this map. The bends measured here are a part in a hundred thousand to a part in ten of the path’s length over a unit of parameter, which covers a gently curving response to a strongly curved one.

What a code cannot know in advance is which row of the map it is on, and that is what makes the choice awkward. On the straight row, taking the parabola costs 17 to 55 per cent more steps. On every bent row at 10⁻¹² and 10⁻¹⁴, taking the line costs a quarter to three quarters more. A fixed choice is wrong by a sixth or more on one of the two, and the data that would decide it — the second difference of the stored answers — is sitting in the history the solver already keeps.

What the steps are worth against the factorisations

All of these counts are inner chord steps, each a residual evaluation and two triangular solves at about 4n24n^2 multiply-adds. The factorisations the run rebuilds every four members are n3n^3/3 each, and at n = 120 five of them cost as much as 50 steps. So on the straight path at 10⁻¹⁰ the line’s twelve steps are a fifth of the run’s arithmetic, and the parabola’s two extra are about three per cent of it.

That puts the map’s differences in proportion, and it is the same proportion what a rebuild is worth argues about from the other side: which of the two costs a sequence is actually paying. On a small dense problem the start matters most where the steps are many — at tight tolerances on bent paths, where the parabola’s saving of thirty steps is a fifth of the run. On a large problem solved iteratively, where there is no factorisation and every member’s cost is its steps, the whole map is the cost, and the order-of-magnitude gap between the previous answer and either extrapolation is what the problem that arrives again means by an asset with a shelf life: the history is worth more than the factorisation.

What this rests on

One family of 120 unknowns at a condition number of ten thousand, with a cubic term; twenty members from t = 0.4 at a drift of 0.02; a factorisation rebuilt every four members; tolerances from 10⁻⁶ to 10⁻¹⁴ on the relative residual; and a bend along one random direction with frequency three. The distances are exact because the roots are constructed. Starts are reported as medians over members four to twenty, the first three being identical for all degrees by construction. Other drifts, other frequencies and larger problems are not measured; the truncation terms say how the floors should move with each.

The claims that have to fail

Two claims, one from each side of the map.

The first is the earlier essay’s prediction taken as a rule: that a tight enough tolerance makes the parabola the better start. On the straight path at 10⁻¹⁴ the line costs 17 and the parabola 23, and the refusal is fed the claim that the parabola needs fewer and fails.

The second is the lesson that essay might be read as teaching: that the line is always the better start because the parabola doubles the stored error. On a path bent by 10⁻² at 10⁻¹² the line costs 107 steps and the parabola 73, and the refusal is fed the claim that the line needs no more and fails.

Still open: choosing the degree from the history

The map has a boundary and a code does not know which side of it a sequence is on. It does have two things that bear on it. The gap between the line’s start and the parabola’s is the second difference of the stored answers, which is the line’s truncation term plus some stored error. And the size of the last correction each member took is an estimate of the stored error. Comparing the two is free.

The other route is to form both starts and evaluate the residual at each, which costs one residual product a member and chooses by the quantity the solve is actually stopped on. Which of the two picks the winning cell of the map more often, what each costs on the cells it gets wrong, and whether either choice ever changes within a run, are measured in the degree the history chooses.

A second question lies past both. Nothing here uses more than three stored answers or asks whether the drift step itself should change: on a bent path at a tight tolerance the line’s floor falls as the square of the step, so halving the drift quarters it, and a code free to choose its parameter spacing faces a trade between members and steps per member that this map does not price.

Where this goes next

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. 10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110⁻⁴10⁻³10⁻²10⁻¹1inner tolerance η, relative residual of the linear solvedistance from the root after the stepd² = 0.00138distance before the step, 0.03721093547231126the number by each point is the iterations it costeleven decades, one landing placedistance before the step0.037its square0.0014where η = 10⁻³ lands0.0025where η = 10⁻¹⁴ lands0.0025iterations for the first354iterations for the second1126the accuracy that is thrown awaymeasured against a root that is known The accuracy that is thrown away A Newton step is the exact answer to a linearised problem, and the linearisation is wrong at second order. So there is a floor under how close the step can land, the floor is the square of where it started, and eleven decades of inner tolerance below it buy the same four digits at four times the price. nothing8.3%the right-hand side16.5%the matrix, slowly85.9%everything100.0%what can be reused: the answerwhat can be reused: the factorisationwhat can be reused: the factorisation, for a whilewhat can be reused: nothingshare of the cost of a sequence that shares nothingwhat 12 members cost in factorisationssame: factorisations1rhs: factorisations1drift: factorisations4independent: factorisations12what changes between the membersdecides what may be carried The problem that arrives again A hundred and thirty essays have solved a system once and measured how wrong the answer was. Almost no computation is shaped like that. A solve is one step of an outer loop, its answer is an input rather than a deliverable, and four quantities treated here as accuracy requirements turn out to be assets with a shelf life.

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