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

A tolerance that reads its own residual

The cheapest constant forcing term costs 980 inner iterations and arrives with a hundred times the forward error of the dearest, which costs 9,358. A rule that sets each step's tolerance from the ratio of the last two residuals costs 1,009 and arrives with neither problem — and it is not a constant, so it does not appear on the curve the constants are compared on.
28 min read 23 figures Where the algebra stops being the arithmeticMeasured, not assertedIdentical algebra, different arithmeticExact ground truth

Worth reading first: The accuracy that is thrown away · The problem that arrives again · The rate the condition number predicts.

The essay on the accuracy that is thrown away ends with a curve that has a bottom, and the obvious next move is to go and sit at the bottom. It is the wrong move, and the reason is visible in the same figure if it is read one column at a time rather than as a shape.

The cheapest constant forcing term on that problem is η = 0.1, at 980 conjugate gradient iterations for the whole solve. The dearest is η = 10⁻¹⁴, at 9,358. Both stop when the outer residual is below 10⁻¹⁰, so by the test that was actually asked, both are correct. But the run at 0.1 arrives with a forward error of 2.43·10⁻⁸ and the run at 10⁻¹⁴ arrives at 2.79·10⁻¹⁰ — eighty-five times better — because a quadratically converging iteration overshoots its stopping test and the tightly solved run overshoots further.

So the two ends of the curve are not two prices for one thing. They are two different things, and the question is whether either of them is what anybody wants.

What each Newton step asked of its linear solve, and what the solve cost, under the adaptive policyThe lower series is the tolerance handed to the inner solve at each step and the upper one is the number of conjugate gradient iterations it took. Under the adaptive rule the first step asks for 0.9 and costs 1 iteration, and the last asks for 0.0042 and costs 271. The whole solve costs 1009 inner iterations across 10 Newton steps and ends at a relative residual of 3.37·10⁻¹¹.0123456789101110⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110³Newton steptolerance asked for, and iterations paiditerations paidtolerance asked forouter residualthe adaptive policy, step by stepNewton steps10inner iterations, total1009first step's cost1last step's cost271final outer residual3.4·10⁻¹¹the rule reads the last two residualsand asks for nothing it cannot use
Fig. 1 Ten Newton steps under a rule that chooses each step’s tolerance from the last two residuals. The lower series is what was asked for, the upper is what it cost, and the dashed line is the outer residual falling.

What the run actually needs, step by step

The measurement in the accuracy that is thrown away says what a step can use: the inner tolerance stops mattering below about the distance to the root, because the linearisation error is the square of that distance.

An outer iteration does not know the distance to the root. It knows something almost as good, and it knows it for free: the ratio of this step’s residual to the last one’s. Near a root that ratio is approximately how much the linearisation is about to be wrong by, and Eisenstat and Walker’s second choice turns it directly into a tolerance,

η_k = γ · ( ‖F_k‖ / ‖F_{k−1}‖ )^α , γ = 0.9, α = (1 + √5)/2

with two safeguards. The first stops the sequence of tolerances falling faster than the residuals justify — if γ·η_{k−1}^α is above 0.1, the new tolerance is not allowed below it, which prevents one lucky step from committing the run to an expensive one. The second is the one this collection cares about and it is a single line: do not ask for an accuracy the outer loop is going to stop before using, which means η is never allowed below half the outer tolerance divided by the current residual.

Both are in the run drawn here, and the second is why the last step costs 271 iterations rather than the 500 a naive reading of the formula would have asked for.

What each Newton step asked of its linear solve, and what the solve cost, under the tight policyThe lower series is the tolerance handed to the inner solve at each step and the upper one is the number of conjugate gradient iterations it took. Under the adaptive rule the first step asks for 10⁻¹⁴ and costs 1775 iterations, and the last asks for 10⁻¹⁴ and costs 1128. The whole solve costs 9358 inner iterations across 9 Newton steps and ends at a relative residual of 1.43·10⁻¹³.01234567891010⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110³Newton steptolerance asked for, and iterations paiditerations paidtolerance asked forouter residualthe tight policy, step by stepNewton steps9inner iterations, total9358first step's cost1775last step's cost1128final outer residual1.4·10⁻¹³the rule reads the last two residualsand asks for nothing it cannot use
Fig. 2 The constant at 10⁻¹⁴ for comparison: the same demand at every step, and a cost that climbs only because the Jacobian gets harder rather than because the answer is getting better.
What each Newton step asked of its linear solve, and what the solve cost, under the loose policyThe lower series is the tolerance handed to the inner solve at each step and the upper one is the number of conjugate gradient iterations it took. Under the adaptive rule the first step asks for 0.1 and costs 4 iterations, and the last asks for 0.1 and costs 133. The whole solve costs 980 inner iterations across 10 Newton steps and ends at a relative residual of 4.09·10⁻¹¹.0123456789101110⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110³Newton steptolerance asked for, and iterations paiditerations paidtolerance asked forouter residualthe loose policy, step by stepNewton steps10inner iterations, total980first step's cost4last step's cost133final outer residual4.1·10⁻¹¹the rule reads the last two residualsand asks for nothing it cannot use
Fig. 3 And the constant at 0.1, which is cheap per step and pays for it in the number of steps — the right arm of the U seen from inside a single run.

What it costs

Ten Newton steps. The tolerances asked for, in order:

0.90 0.76 0.58 0.37 0.18 0.053 0.021 0.024 0.0061 0.0042

and the inner iterations paid, in the same order:

1 1 2 5 17 119 160 176 257 271

The first four steps of a Newton solve on a matrix with a condition number of 10⁵ cost nine conjugate gradient iterations between them. The last two cost 528. The total is 1,009, against 9,358 for the run that solved every step to 10⁻¹⁴, and the outer residual history is

1.0 → 3.6·10⁻¹ → 2.2·10⁻¹ → 8.1·10⁻² → 2.6·10⁻² → 4.5·10⁻³ → 4.5·10⁻⁴ → 4.8·10⁻⁵ → 2.2·10⁻⁶ → 1.2·10⁻⁸ → 3.4·10⁻¹¹

which is one more outer step than the fully solved run took, and a ninth of the work.

Total inner iterations for a whole inexact Newton solve, against the constant forcing termEvery point is a complete solve of the same problem to the same outer tolerance of 10^-10. At η = 10⁻¹⁴ it takes 9358 conjugate gradient iterations across 9 Newton steps; at η = 0.1 it takes 980 across 10. The left arm is oversolving and the right arm is too many outer steps. The open circle is the adaptive rule, which is not a constant: it costs 1009 iterations and reaches 3.37·10⁻¹¹.10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110²10³10⁴10⁵constant forcing term ηtotal inner iterationsthe adaptive ruleoversolvingstarving the outer loopone problem, twelve budgetsη = 10⁻¹⁴, inner iterations9358cheapest constant0.1its inner iterations980adaptive rule, iterations1009adaptive final residual3.4·10⁻¹¹outer tolerance asked for10⁻¹⁰a tolerance is a cost decisionand its optimum is not machine precision
Fig. 4 The rule as a point beside the curve of constants. It is not on the curve because it is not a constant, and putting it on the same axes is the only honest way to compare them.

Why no constant does this

The temptation is to say the rule is a way of finding the best constant automatically. It is not, and the sequence of tolerances above is the proof: they span two and a half orders of magnitude inside a single run. A constant is one number. Whatever it is, it is too tight for the first four steps or too loose for the last two.

Set it at 0.9 and the early steps are free and the late ones never converge quadratically; the run takes thirty steps. Set it at 4·10⁻³ and the last two steps are right and the first four cost several hundred iterations each for a step that lands in the same place anyway. Set it at 0.1 — the measured optimum — and both of those are half true, which is what an optimum of a U is.

The rule is not interpolating between them. It is doing something no constant can do, which is to change during the run, and the quantity it changes in response to is one the run has already computed for another reason.

A single Newton step solved to eleven inner tolerances, against how far the resulting point is from the rootThe iterate is 1.03 from a root that is known exactly by construction. The same linear system is solved to relative residuals from 0.3 down to 10⁻¹⁴, at 53 and 849 conjugate gradient iterations, and the resulting point is 0.5725 and 0.5071 from the root. The curve is flat below about 10⁻³: the linearisation is wrong at second order, so the step cannot land closer than the square of the distance it started at — 1.055 — however exactly it is computed.10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110⁻¹110¹inner tolerance η, relative residual of the linear solvedistance from the root after the stepd² = 1.05distance before the step, 1.0353219543849the number by each point is the iterations it costeleven decades, one landing placedistance before the step1its square1.1where η = 10⁻³ lands0.51where η = 10⁻¹⁴ lands0.51iterations for the first219iterations for the second849the accuracy that is thrown awaymeasured against a root that is known
Fig. 5 Why the early steps can be free: at this iterate the plateau is at 5.07·10⁻¹ and every tolerance from 10⁻² down lands on it.
A single Newton step solved to eleven inner tolerances, against how far the resulting point is from the rootThe iterate is 0.0025 from a root that is known exactly by construction. The same linear system is solved to relative residuals from 0.3 down to 10⁻¹⁴, at 109 and 1129 conjugate gradient iterations, and the resulting point is 2.837·10⁻⁴ and 1.2·10⁻⁵ from the root. The curve is flat below about 10⁻³: the linearisation is wrong at second order, so the step cannot land closer than the square of the distance it started at — 6.234·10⁻⁶ — however exactly it is computed.10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²inner tolerance η, relative residual of the linear solvedistance from the root after the stepd² = 6.23·10⁻⁶distance before the step, 0.00251093397131129the number by each point is the iterations it costeleven decades, one landing placedistance before the step0.0025its square6.2·10⁻⁶where η = 10⁻³ lands1.2·10⁻⁵where η = 10⁻¹⁴ lands1.2·10⁻⁵iterations for the first339iterations for the second1129the accuracy that is thrown awaymeasured against a root that is known
Fig. 6 And why the late ones cannot: here the plateau is at 1.2·10⁻⁵ and a tolerance of 10⁻² is genuinely 22 per cent short of it.

The comparison that has to be made on two numbers

The awkward part of this comparison, and the reason the refusal in this essay is worded the way it is, is that a single number cannot express it.

  • Against the cheapest constant, the rule costs 3 per cent more work (1,009 against 980) and arrives with a comparable forward error.
  • Against the dearest constant, the rule costs a ninth of the work and arrives with a hundred times the forward error.

Neither of those on its own is a recommendation. What makes the rule the right default is the pair together with a third fact: the cheapest constant is only knowable by running the whole sweep, and the sweep is specific to this problem, this conditioning and this outer tolerance. Move the outer tolerance from 10⁻¹⁰ to 10⁻¹² and the minimum moves; the rule does not have to be told.

Total inner iterations for a whole inexact Newton solve, against the constant forcing termEvery point is a complete solve of the same problem to the same outer tolerance of 10^-12. At η = 10⁻¹⁴ it takes 9358 conjugate gradient iterations across 9 Newton steps; at η = 0.1 it takes 1256 across 12. The left arm is oversolving and the right arm is too many outer steps. The open circle is the adaptive rule, which is not a constant: it costs 1206 iterations and reaches 4.8·10⁻¹³.10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110²10³10⁴10⁵constant forcing term ηtotal inner iterationsthe adaptive ruleoversolvingstarving the outer loopone problem, twelve budgetsη = 10⁻¹⁴, inner iterations9358cheapest constant0.1its inner iterations1256adaptive rule, iterations1206adaptive final residual4.8·10⁻¹³outer tolerance asked for10⁻¹²a tolerance is a cost decisionand its optimum is not machine precision
Fig. 7 The same sweep two decades tighter, where the whole curve lifts and its minimum walks left. Any constant tuned on the previous figure is now the wrong constant.
Total inner iterations for a whole inexact Newton solve, against the constant forcing termEvery point is a complete solve of the same problem to the same outer tolerance of 10^-8. At η = 10⁻¹⁴ it takes 8230 conjugate gradient iterations across 8 Newton steps; at η = 0.1 it takes 730 across 8. The left arm is oversolving and the right arm is too many outer steps. The open circle is the adaptive rule, which is not a constant: it costs 822 iterations and reaches 4.75·10⁻⁹.10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110²10³10⁴10⁵constant forcing term ηtotal inner iterationsthe adaptive ruleoversolvingstarving the outer loopone problem, twelve budgetsη = 10⁻¹⁴, inner iterations8230cheapest constant0.1its inner iterations730adaptive rule, iterations822adaptive final residual4.7·10⁻⁹outer tolerance asked for10⁻⁸a tolerance is a cost decisionand its optimum is not machine precision
Fig. 8 And two decades looser, where it walks the other way.

What the rule cannot see

This collection’s habit is to say where a rule fails, and this one has a clean answer: it cannot see cost.

The forcing term decides how much of an inner solve to buy. The rule prices that decision in the only currency it can observe — the residual, which is a statement about accuracy — and it never asks what an inner iteration costs relative to an outer step. On this problem that is harmless, because an outer step is a residual evaluation and a Jacobian assembly and the inner solve is hundreds of matrix–vector products, so the inner side dominates and the accuracy question and the cost question have the same answer.

Change that ratio and they come apart. If the residual evaluation were the expensive thing — a full physics evaluation, say, with a cheap Jacobian — then more inner work per step would be worth buying, because it saves outer steps and outer steps are what costs. The rule would keep asking for the same tolerances and would be wrong, quietly, by whatever that ratio is.

The essay on what a rebuild is worth is the same observation about a different object, and there it is not harmless: the rule that reads the iteration count of a preconditioned solve loses to a fixed period at both ends of the range, because what it cannot see is exactly what decides the answer there.

The cheapest rebuild period for one drifting sequence, against what a rebuild costsOne sequence, one drift rate, one preconditioner — and six answers, because the answer is not a property of the sequence. Costed in iteration-equivalents, the optimal period runs from every 1 member at a setup worth 5 iterations to every 12 at a setup worth 200. A dense Cholesky at this size is worth 6.7 iterations, which is at the left of the axis, so for it the answer is always to rebuild. The rule that rebuilds when a solve takes 1.5 times what the last fresh one did beats the best fixed period at 1 of the 6 ratios and loses at the rest, because it cannot see the setup cost at all.10¹10²10³03691215what one rebuild is worth, in preconditioned iterationscheapest number of members between rebuildsa dense Cholesky here is worth 6.7 iterationsringed: where the growth rule beats every fixed periodcheapest period, by setup costsetup worth 51setup worth 102setup worth 203setup worth 506setup worth 1008setup worth 20012how long to keep itis a question about what it cost to build
Fig. 9 The same shape of rule failing, in the essay that measures it: an optimum that walks with a cost the rule has no access to.
The cost of a drifting sequence of nonlinear solves, against how often the Jacobian is refactorisedTwenty members, each warm-started from the last, each solved by a chord iteration on a factorisation that may be several members old. Refactorising at every member costs 16.42 MFlop; refactorising every 5 costs 9.27. Past a period of 20 the chord iteration stops converging altogether, which is drawn as an open circle on the ceiling rather than omitted. The filled square is the rule that refactorises when the observed contraction ratio exceeds 0.2: 4 factorisations, 9.22 MFlop, and it was never told the drift rate.024681012141618202210⁶10⁷10⁸members served by one factorisationmultiplications for the whole sequencedoes not convergethe contraction ruledrift 0.01 a memberevery member1.6·10⁷every 5 members9.3·10⁶contraction rule9.2·10⁶its factorisations4cliff at a period of20a factorisation has a shelf lifeand the cliff is past the optimum
Fig. 10 And the rule that does work, on the object where the free measurement happens to be the right one.

The safeguard that is one line

It is worth isolating the second safeguard, because it is where the collection’s own subject appears inside somebody else’s method.

Without it, the formula on the last step of a converging run asks for a tolerance proportional to the square of a residual that is already at 10⁻⁸ — which is to say, for something near 10⁻¹³ relative, on a step whose result will be tested at 10⁻¹⁰ and then accepted. The tolerance is not wrong; it is simply for a quantity nobody is going to look at.

With it, η is floored at half the outer tolerance divided by the current residual: exactly the accuracy that makes the next outer residual land at the tolerance, and no more. On the run above that turns the last step’s demand from a number the formula produced into 4.2·10⁻³, and the step costs 271 iterations rather than several hundred.

It is a line of code and it is worth about a fifth of the whole solve, and the thing it encodes is the field’s sentence: an inner solve is worth exactly as much accuracy as the outer loop is going to use.

What the solver reported, and what it achievedFinal relative residual and final relative error against the working precision, on a logarithmic vertical axis. The residual sits at the stopping tolerance at every precision — the method converged, by every test available to it. The error runs from 5.26·10⁻¹⁴ at 53 bits to 0.00804 at 8, tracking the unit roundoff, which is drawn beside it.614223038465410⁻¹³10⁻¹⁰10⁻⁷10⁻⁴working significand bitsrelative sizeerrorresidualuthe gap the solver cannot seeerror ÷ residual at 24 bits4.1·10⁵error ÷ residual at 16 bits3.6·10⁷error ÷ residual at 8 bits1.9·10¹⁰every convergence test passesand the answer is wrong in proportion to u
Fig. 11 Why the outer test is a residual and not an error, from the essay that established the difference. The safeguard is written in the quantity the loop can see, which is the same quantity that cannot see the error.
Backward and forward error against the condition numberA log–log plot over twelve decades of condition number. The backward error is a flat line at ten to the minus sixteen; the forward error rises in proportion to the condition number.110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method
Fig. 12 And the two errors themselves. The rule is about the left-hand one; the eighty-five-fold difference in forward error between the two constants is the right-hand one.

The first four steps cost nine iterations

It is worth pausing on one line of the table above, because it is the part that sounds wrong.

The first four Newton steps of this solve — on a 200×200 system whose Jacobian has a condition number of 10⁵, where a single conjugate gradient solve to machine precision costs over a thousand iterations — cost one, one, two and five iterations. Nine in total. A tenth of one per cent of what the fully solved run spends on the same four steps.

Nothing has been approximated away. Those are real conjugate gradient solves of the real Newton systems; they simply stop after a step or two because the tolerance they were given is 0.9, 0.76, 0.58 and 0.37, and a single step of conjugate gradients from a zero start already reduces the residual by more than that on this problem. What the rule has noticed is that the outer iteration is so far from the root that a direction is all a step can use, and the first conjugate gradient iterate is the steepest-descent direction scaled to minimise the quadratic — which is a perfectly good direction.

The outer residuals over those four steps run 1.0 → 0.36 → 0.22 → 0.081 → 0.026. That is a factor of forty, for nine matrix–vector products, from a method that has not yet been asked for a single accurate solve.

The last two steps then cost 528 iterations between them, and every one of those is needed: they are the steps where the outer residual goes from 2.2·10⁻⁶ to 3.4·10⁻¹¹ and the plateau has dropped below what a loose solve can reach.

The work is where the accuracy survives. That is the entire content of the staircase, and it is what a constant cannot express.

The filter 16 conjugate gradient steps apply, measured and predictedFilter factors against the singular-value index. The factors measured off the iterate and the polynomial predicted from the recurrence coefficients agree to 1.2·10⁻¹¹ and are drawn as one curve. It rises above one — 1.203 at its largest — and changes direction several times. Tikhonov's filter at the matching cutoff is monotone and never exceeds one.081624324048566400.250.50.7511.25index kfilter factoronezeroCG, both routesTikhonovone of these is not a weightlargest CG factor1.2measured vs predicted1.2·10⁻¹¹largest Tikhonov factor1two routes to the same curveand a curve that goes above one
Fig. 13 What one Krylov step actually buys, from the field that draws it as a filter: the first iterate is already a direction, and directions are what an early Newton step needs.
Two Krylov methods against products with A, at a kernel shift of 0Two error curves against the number of products with A, on a logarithmic vertical axis. The Arnoldi method reaches 0.1477 after 3 products and is 1089 by the end of the run. The bidiagonal method reaches 0.1426 after 40 and degrades far more slowly.181522293643505764717810⁻¹110¹10²10³products with Arelative errorArnoldi's best: 3Arnoldibidiagonalwhat a step buysArnoldi's best0.15products to reach it3bidiagonal's best0.14products to reach it40a tenth of the work to the same answerand no time at all spent there
Fig. 14 And the same basis a few steps later, where it has started resolving the parts of the spectrum a late Newton step depends on.
GMRES on the Laplacian and on the cyclic shift, both 40×40A semi-logarithmic plot of relative residual against iteration. One curve falls steadily; the other is flat at one for every step until the last, where it drops to zero.071421283510⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1iteration‖r‖ / ‖b‖Laplaciancyclic shiftno progress at allevery eigenvalue of the shift is on the unit circleand it predicts nothing
Fig. 15 A reminder that the inner solver’s cost is not predictable from the spectrum alone, which is why the rule reads what the iteration did rather than what the matrix looks like.

Where this sits beside the collection’s other rules

Three parameter-choice rules have been measured here now, and it is worth putting them side by side, because they fail in different places and the pattern is not obvious.

A regularisation parameter is chosen without knowing the noise level, and every published rule for it is a heuristic that can be scored against a truth that exists only because the problem was constructed. Some of them are badly wrong on some problems.

A step count used as a regularisation parameter degrades gently: being one step out costs a few per cent, which is a different kind of robustness from being right.

A forcing term is chosen with the answer unknown too — and unlike the first two, being wrong costs work rather than accuracy. There is no bad answer at the end of a Newton run with a badly chosen forcing term, only a slow one or a wasteful one. That is what makes it the easiest of the three and the one where an automatic rule is uncontroversial.

The L-curve, and where four rules put λThe norm of the solution against the norm of its residual, on logarithmic axes, as λ sweeps eight decades. The curve has a corner: to the left of it the noise is being amplified and to the right the signal is being thrown away. Four points are marked — the three rules that use only the data, and the oracle, which requires the exact answer and is not a method.10⁻¹110¹10²10³10⁴10⁵‖Ax − b‖‖x‖the oraclediscrepancyL-curvegeneralisedscored against a truth none hasoracle, relative error0.14discrepancy principle, as a multiple1L-curve corner, as a multiple1.3generalised cross-validation, as a multiple1the oracle needs the exact answer and is not a methodit is the reference the others are scored on
Fig. 16 The rules for choosing a regularisation parameter, scored in the field that measures them. Those rules are choosing between answers; this one is choosing between prices.
Four knobs on one problem at 1.0% noiseRelative error against the fraction of each method's own range, on a logarithmic vertical axis. A truncation, a Tikhonov parameter, a conjugate gradient step count and a randomised rank each have an interior minimum, and the four minima are 0.1445, 0.1406, 0.1426, 0.1449 — a spread of 3%. The horizontal line is the best of them.00.250.50.75110⁻¹110¹10²10³fraction of the method's own rangerelative errorfloor 0.141truncation KTikhonov λCGLS steprandomised rankfour methods, one floortruncation K0.14Tikhonov λ0.14CGLS step0.14randomised rank0.14four knobs from four fieldsand one obstruction underneath them
Fig. 17 And the four knobs with one floor under them. A forcing term is not on that floor, because what it controls is not how much of the data to believe.
Conjugate gradients on an ill-posed problem at 1.0% noiseTwo curves against the step count on a logarithmic vertical axis. The relative residual falls at every one of the 60 steps without exception. The error against the true signal falls to 0.1426 at step 20 and then climbs, reaching 1.11 by the end — 7.8 times its best value.0816243240485610⁻²10⁻¹1steprelative sizeleast error: 20discrepancy stop: 7errorresidualthe knob is an integerleast error, at step20error there0.14error at step 601.1the residual falls at every stepthe error turns and keeps rising
Fig. 18 The step count as a knob, from the field where stopping early is the regularisation. Stopping an inner solve early is a cost decision; stopping an outer one early is an answer.

What the rule assumes about the outer iteration

The rule reads the ratio of consecutive residuals and turns it into a tolerance, and that step carries an assumption worth making explicit: that the residual ratio is a usable proxy for how wrong the linearisation is about to be.

Near a simple root of a smooth problem it is a good one, which is the case the formula was derived for and the case measured here. Away from one it can be poor in either direction — a step that happens to reduce the residual sharply is read as evidence that the linearisation is good, and the rule tightens; a step that stalls for a reason unrelated to the linearisation is read as evidence that it is bad, and the rule loosens.

Both of those are why the safeguards exist. The first stops one lucky step from committing the run to an expensive tolerance, and it is not a numerical nicety — it is the rule declining to believe a single observation. The second stops the last step from being solved past the point the outer loop will look at.

What neither safeguard can do is notice that the proxy has stopped being a proxy, and the honest statement of this rule’s scope is that it is a heuristic with two guards on it rather than a measurement of the quantity it wants.

What is checked

Four things are asserted about this rule rather than described, and each of them is fed a case it must refuse.

That the rule costs under an eighth of the fully solved run — 1,009 against 9,358 — with a final residual below the tolerance it was given.

That its tolerances actually move: above 0.5 at the first step and below 0.05 at the last, which is what makes it not a constant.

That the cost profile follows: a handful of iterations at the first step and hundreds at the last, so the work is spent where the accuracy survives.

And that the effect needs something to save. The refusal is a problem at a condition number of 4, where the inner solve costs a handful of iterations at any tolerance: there the claim that oversolving costs a factor of eight is fed to the assertion and fails, which is what stops the main result from being a statement about arithmetic in general.

Conjugate gradients at κ = 102, against the bound κ permitsA semi-logarithmic plot of the relative A-norm error against iteration count. The measured curve falls below a smooth dashed curve showing the classical condition-number bound.0408012016020024010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration‖e‖_A / ‖e₀‖_Ameasuredκ bound58 steps40×40, spectrum spread evenly in logbound permits 142
Fig. 19 The refusal’s problem: a conditioning at which the inner solve is cheap however it is asked for, and there is nothing for a forcing term to save.
Conjugate gradients at κ = 105, against the bound κ permitsA semi-logarithmic plot of the relative A-norm error against iteration count. The measured curve falls below a smooth dashed curve showing the classical condition-number bound.0408012016020024010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration‖e‖_A / ‖e₀‖_Ameasuredκ bound168 steps40×40, spectrum spread evenly in logbound permits 4479
Fig. 20 And the one the measurement is made on, where the same decade of tolerance costs a hundred iterations.
LSQR steps to a normal residual of 10⁻¹², with and without a sketched preconditionerTwo curves against κ(A). The unpreconditioned solve takes 15, 22, 32, 59, 150 steps as the conditioning worsens, and at the worst one it does not reach the tolerance inside 150. The preconditioned solve takes 10, 10, 10, 10, 10 — flat across eight decades. Both return the same vector, to the accuracy the problem allows: the preconditioned answer and the direct one differ by about κ(A)·u at every κ, 5.7·10⁻⁶ at the worst. The SAME sketch used as an answer instead of as a preconditioner is 4.5 away.10²10⁴10⁶10⁸10¹⁰110¹10²10³condition number of the matrixLSQR steps to 10⁻¹²no preconditionersketchedthe cost, not the answersteps, preconditioned10steps, without150answer gap, preconditioned5.7·10⁻⁶κ(A)·u at the worst κ1.1·10⁻⁶answer gap, sketch-and-solve4.5one sketch, two things to do with itand only one of them moves the answer
Fig. 21 The other way to make an inner solve cheap, which changes the size of the prize and not the shape of the argument.
What 12 members of a sequence cost, by what changes between themEvery bar is 12 solves of an 120×120 system, costed in multiplications with a dense Cholesky at n³/3 and a solve at 4n². When nothing changes the answer is reused and the cost is one factorisation. When only the right-hand side changes, one factorisation serves every member — 16.5 per cent of the independent cost, with every solve still at a relative residual of 1.54·10⁻¹³. When the matrix drifts, the factorisation is reusable for a while and the while has to be measured: 4 factorisations for 12 members. When everything changes, nothing carries.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
Fig. 22 And the field’s ledger. The forcing term is the first of its four assets and the only one that costs nothing to keep.
Chord steps per member of a drifting sequence, with the factorisation rebuilt every 4Each point is one member of a continuation, warm-started from the previous member's answer and solved with a factorisation that is between zero and 3 members old. The lower series is the same sequence with a fresh factorisation at every member, which costs 6 to 5 steps throughout. The kept run costs 6 steps on a fresh factor and 12 at its worst, for 5 factorisations against 20.03691215182103691215member of the sequencechord steps to reach the tolerancea fresh factorisation each memberthe ringed points are the refactorisationsrebuilt every 4factorisations5chord steps160worst member's steps12multiplications1.2·10⁷with a fresh factor each time1.8·10⁷a factor is cheapest the member it was built forand dearest the member before it is replaced
Fig. 23 The second, which does.

Where this goes next

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 this collection has treated as accuracy requirements turn out to be assets with a shelf life. 10⁻²10⁻¹110¹10²10³10⁴‖Ax − b‖‖x‖the oraclediscrepancyL-curvegeneralisedscored against a truth none hasoracle, relative error0.11discrepancy principle, as a multiple1.1L-curve corner, as a multiple2.3generalised cross-validation, as a multiple1the oracle needs the exact answer and is not a methodit is the reference the others are scored on Choosing without knowing Three published rules for choosing a regularisation parameter, scored against an oracle that requires the exact answer and is therefore not a method. Generalised cross-validation lands on the oracle's λ exactly; the discrepancy principle costs 6%; the L-curve costs 129%. And told a noise level ten times too small, the discrepancy principle's error goes from 0.112 to 10,449.

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.

Conjugate gradientsFlop countForcing termInexact newtonKrylov subspaceNewton iterationQuadratic convergenceStopping criterionWarm start