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

A floor with a cliff at one

Inexact Newton's adaptive forcing rule is used with a floor: never ask the inner solve for less than c times the outer tolerance, relative to the current residual, with c a half. Swept from a hundredth to ten, the constant trades with no knee at all — the forward error rises in proportion to c, the inner work falls by a few per cent a decade — and then, just past one, the run stops converging: at c = 3 it hits the outer limit on four problems of five, having asked every step for less than the stopping test needs. And the accuracy the floor gives up at c = ½ is no planning number: across five problems and four tolerances it runs from nothing to a factor of 48,000.
19 min read 5 figures Measured, not assumedWhose fault is itExact ground truth

Worth reading first: The accuracy that is thrown away · A stopping test is a race.

One line that buys a quarter of the run found a line inside the adaptive forcing rule of inexact Newton that no published statement of the rule carries. Newton’s method solves each linear step only approximately, to a relative residual η chosen from the ratio of the last two nonlinear residuals, and the line puts a floor under it: never ask for an η below c⋅tol⋅∥b∥/∥F∥c \cdot \mathrm{tol}\cdot\lVert b\rVert/\lVert F\rVert, with c=12c = \tfrac12. The reasoning is that the outer loop will stop when ∥F∥/∥b∥\lVert F\rVert/\lVert b\rVert falls below tol, so accuracy past that point is accuracy nobody reads. Measured, the floor saved 9 to 27 per cent of the inner work and cost 23 to 2,600 times the forward error — accuracy the stopping test never asked for, and both runs passed the test.

The essay’s open questions were about the half. It is arbitrary. Swept, would the saving and the accuracy lie on one curve with a knee — a value of c past which the saving stops growing and the accuracy keeps falling — or on a straight line? And is the accuracy premium, the factor by which the unfloored run is more accurate, stable enough across problems for a caller to plan on?

The curve has no knee. It has a cliff, and it is at one.

The constant, swept

The problem is the one the forcing essays have used throughout: Newton’s method on F(x)=Ax+λx3−bF(x) = Ax + \lambda x^3 - b with 200 unknowns, AA symmetric positive definite at condition number 10510^5 and λ = 3, each step solved by conjugate gradients. The adaptive rule runs with the floor at nine values of c, from 0.01 to 10, and without it; every count is a count of matrix–vector products, and the forward error is measured against the known root.

One line in the adaptive rule: the floor on the last step's forcing termAgainst the outer tolerance on logarithmic axes: the forward error each run reaches, and its total inner iterations drawn on the same axis as a fraction of its range. With the floor the run reaches 1.97·10⁻¹⁰ in 1206 inner iterations at an outer tolerance of 1e-12; without it, 5.25·10⁻¹³ in 1657. Both runs stop when the outer relative residual is below the tolerance, and both do. The floor saves between 9 and 27 per cent of the inner work and costs up to 2636 times the forward error.what one line doesinner work saved, worst case0.09best case0.27forward error cost, worst263610⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴outer toleranceforward errorerror, with the floorerror, without itinner work, rescaledthe grey diagonal is the residual the test asked forboth runs meet it and one is far more accurate
Fig. 1 The floor on and off at four outer tolerances, as the earlier measurement drew it: inner iterations saved against forward accuracy given up.
The last-step floor's constant c, swept, at an outer tolerance of 10⁻⁸: forward error and inner iterations over the unguarded run'sInexact Newton with the adaptive forcing rule on a 200-unknown problem at condition number 10⁵, its inner tolerance floored at c times the outer tolerance times ‖b‖ over ‖F‖. On logarithmic axes against c from 0.01 to 10: the forward error over the unguarded run's, and the inner iterations over its 1109. c = 0.01: error 44×, 983 inner, 10 outer; c = 0.03: error 148×, 932 inner, 10 outer; c = 0.1: error 331×, 897 inner, 10 outer; c = 0.3: error 1677×, 844 inner, 10 outer; c = 0.5: error 2636×, 822 inner, 10 outer; c = 1: error 4979×, 782 inner, 10 outer; c = 3: error 18112×, 774 inner, 79 outer, not converged; c = 10: error 43374×, 733 inner, 79 outer, not converged.tol 10⁻⁸unguarded inner iterations1109c = 1, error ÷ unguarded497910⁻²10⁻¹110¹10⁻¹110¹10²10³10⁴10⁵c, the floor's constantover the unguarded runerror ÷ unguardedinner iterations ÷ unguardedopen dots: the run did not convergea trade with no knee, and then a cliff
Fig. 2 At one outer tolerance, the forward error and the inner iterations over the unfloored run’s, against the floor’s constant c. Open dots mark runs that did not converge. The dial sets the tolerance.

At an outer tolerance of 10−810^{-8}, the unfloored run takes 1,109 inner iterations and reaches a forward error of 1.2·10⁻⁹. With the floor at c = 0.01 it takes 983 and is 44 times less accurate; at 0.1, 897 and 331 times; at 0.5 — the constant in use — 822 and 2,636 times; at 1, 782 and 4,979 times. Each decade of c costs about a decade of forward error, and buys eight to ten per cent of the inner work.

That is a trade with no knee in it. The error is linear in c because the floor sets the last step’s relative residual, and the error of a well-conditioned root is proportional to the residual it was stopped at. The saving is logarithmic in c because conjugate gradients spends a roughly constant number of iterations per decade of residual — the fact a guess worth two per cent found limiting what any starting guess can buy — so a floor ten times coarser saves one decade’s worth of the last step’s iterations and nothing else. Neither curve bends. Choosing c on this range is choosing a point on a straight line in log–log coordinates, and nothing about the line says where.

Then c = 3. The inner work falls a little further, to 774 — and the run takes 79 outer steps, the cap, without meeting the tolerance. At c = 10 the same. Turn the dial to other tolerances and the pattern repeats: at 10−610^{-6} the run at c = 3 reaches the tolerance only in 39 outer steps and at c = 10 not at all; at 10−1010^{-10} and 10−1210^{-12}, both stall at the cap.

All of it is the last step

The saving is not spread over the run. At 10−810^{-8} the unfloored run spends 371 of its 1,109 inner iterations on its last step. With the floor at c = 0.01 the last step takes 245; at 0.1, 159; at 0.5, 84; at 1, 44. Every other step is identical, iteration for iteration, and the difference in the total is exactly the difference in the last step. That is the floor doing what its comment says — it only binds when the ratio rule has asked for an accuracy below the one the stopping test needs, which happens once, at the end — and it is why the saving is bounded: the most it can ever save is the unfloored run’s last step, a third of the run here.

It also says why the forward error is so sensitive to it. The last step is the one that places the iterate. Everything before it moves the iterate towards the root at Newton’s quadratic rate, and the last step’s inner tolerance decides where, inside the final basin, it comes to rest. Solved to the ratio rule’s own forcing term — 371 iterations, a relative residual far below the test — it lands almost on the root. Solved to the floor, it lands wherever the floor allows. A stopping test is a race described the general shape: two tolerances, one on the inner solve and one on the outer loop, and a run whose outcome depends on which is crossed first. Here the floor fixes the order of the race, and c sets the margin.

The same trade at 10⁻¹²

The last-step floor's constant c, swept, at an outer tolerance of 10⁻¹²: forward error and inner iterations over the unguarded run'sInexact Newton with the adaptive forcing rule on a 200-unknown problem at condition number 10⁵, its inner tolerance floored at c times the outer tolerance times ‖b‖ over ‖F‖. On logarithmic axes against c from 0.01 to 10: the forward error over the unguarded run's, and the inner iterations over its 1657. c = 0.01: error 11×, 1346 inner, 11 outer; c = 0.03: error 42×, 1294 inner, 11 outer; c = 0.1: error 93×, 1262 inner, 11 outer; c = 0.3: error 219×, 1225 inner, 11 outer; c = 0.5: error 376×, 1206 inner, 11 outer; c = 1: error 1005×, 1168 inner, 11 outer; c = 3: error 2229×, 1179 inner, 79 outer, not converged; c = 10: error 9549×, 1139 inner, 79 outer, not converged.tol 10⁻¹²unguarded inner iterations1657c = 1, error ÷ unguarded100510⁻²10⁻¹110¹10⁻¹110¹10²10³10⁴10⁵c, the floor's constantover the unguarded runerror ÷ unguardedinner iterations ÷ unguardedopen dots: the run did not convergea trade with no knee, and then a cliff
Fig. 3 The same sweep at an outer tolerance of 10⁻¹²: forward error and inner iterations over the unfloored run’s, against c.

At the tightest tolerance the shape is the same and the numbers are larger. The unfloored run takes 1,657 inner iterations, 548 of them on its last step, and reaches a forward error of 5.3·10⁻¹³. With the floor at 0.01 it takes 1,346 and is eleven times less accurate; at 0.1, 1,262 and 92 times; at 0.5, 1,206 and 377 times; at 1, 1,168 and a thousand times. At 3 and 10 the run stalls at the cap, each stalled step costing a single inner iteration: the floor at those constants asks for so little that conjugate gradients meets it in one product, and the outer loop takes a step that barely moves.

That last detail is the stall seen from inside. A run past the cliff is not expensive — its seventy-nine steps cost about as much inner work as the converging runs’ ten — it is futile. Each step solves a linear problem to an accuracy that cannot produce a residual below the test, and the loop has no way to learn that from anything it measures. It is the mirror image of the refinement run in the residual turns before the error doubles, which also failed to stop — but there the failure to stop was information, the signature of a saddle, and here it is only a floor set above the line it was meant to sit under. A loop that reports “did not converge” cannot tell a caller which of the two it is, and a residual history that has gone flat at a level just above the tolerance is the one sign that it is the second: a floor-induced stall sits a little above the tolerance step after step — 1.4 and 4.4 times it at c = 3 and 10 on the standing problem at 10⁻⁸ — where a genuinely hard problem’s residual wanders.

Why the cliff is at one

The floor asks each step for a relative residual no smaller than c tol ∥b∥/∥F∥c\,\mathrm{tol}\,\lVert b\rVert/\lVert F\rVert. A step solved exactly to that relative residual reduces the nonlinear residual to about c tol ∥b∥c\,\mathrm{tol}\,\lVert b\rVert, plus the second-order error of the linearisation. The stopping test wants ∥F∥<tol ∥b∥\lVert F\rVert < \mathrm{tol}\,\lVert b\rVert. So with c below one, a step solved to the floor lands below the test’s threshold and the loop stops; with c above one, a step solved to the floor lands above it, the next step’s floor is recomputed from the new, slightly smaller residual and asks for about the same absolute accuracy again, and the iteration crawls towards the threshold by whatever the conjugate-gradients solve overshoots its tolerance by. It may arrive after many steps, or not before the cap.

Outer Newton steps against the floor's constant, on five problems at an outer tolerance of 10⁻⁸On logarithmic axes. Each line is one problem, conditioning and nonlinearity as labelled; the outer loop is capped at eighty steps. κ 10⁵, λ 3: 10, 10, 10, 10, 10, 10, 79, 79; κ 10³, λ 3: 8, 8, 8, 8, 8, 8, 22, 79; κ 10⁷, λ 3: 9, 9, 9, 9, 9, 10, 79, 79; κ 10⁵, λ 0.3: 9, 9, 9, 9, 9, 9, 79, 79; κ 10⁵, λ 30: 9, 9, 9, 9, 9, 9, 79, 79 for c = 0.01, 0.03, 0.1, 0.3, 0.5, 1, 3, 10. Every problem converges in its usual count up to c = 1 and stalls at the cap from c = 3 or 10.10⁻²10⁻¹110¹10¹10²c, the floor's constantouter Newton stepsκ 10⁵, λ 3κ 10³, λ 3κ 10⁷, λ 3κ 10⁵, λ 0.3κ 10⁵, λ 30eighty is the cap: the run stalleda floor above the test is a floor the test cannot pass
Fig. 4 Outer Newton steps against the floor’s constant on five problems at an outer tolerance of 10⁻⁸; eighty is the cap.

Across five problems — conditioning 10310^3, 10510^5 and 10710^7, nonlinearity λ from 0.3 to 30 — the outer step count at 10−810^{-8} is flat from c = 0.01 to c = 1 on every one: 10, 8, 9, 9 and 9 steps, the same as without the floor except for one extra step on the worst-conditioned problem at c = 1. At c = 3 four of the five run to the cap and the fifth needs 22 steps where it needed 8. At c = 10 all five stall.

So the floor’s constant has a hard upper limit, and the limit is not a tuning choice: it is where the floor stops being below the stopping test. The half in use sits a factor of two inside it. A code that raised it to buy more saving — the natural thing to try, given that the saving grows with c — would lose nothing detectable until c crossed one, and then lose convergence entirely.

The premium is not a planning number

The earlier essay’s last open question was whether the accuracy the floor gives up is stable enough to be relied on — in which case a caller could decide once whether the floor is worth it — or varies enough to be useless.

What the floor at c = ½ saves and what it costs, on five problems at four outer tolerancesTwenty runs: five problems, conditioning 10³ to 10⁷ and nonlinearity 0.3 to 30, at outer tolerances 10⁻⁶ to 10⁻¹². Horizontally, the share of inner iterations the floor saves; vertically, on a logarithmic axis, the forward error with the floor over the error without it. The premium runs from 1.00 to 4.81·10⁴ and the saving from 0.0% to 37.7%, with no relation between them: κ 10⁵, λ 3 at 10⁻⁶, 19.6% and 31.7; κ 10⁵, λ 3 at 10⁻⁸, 25.9% and 2636; κ 10⁵, λ 3 at 10⁻¹⁰, 9.0% and 23.2; κ 10⁵, λ 3 at 10⁻¹², 27.2% and 376; κ 10³, λ 3 at 10⁻⁶, 32.5% and 1221; κ 10³, λ 3 at 10⁻⁸, 11.3% and 12.6; κ 10³, λ 3 at 10⁻¹⁰, 31.7% and 4.81·10⁴; κ 10³, λ 3 at 10⁻¹², 18.9% and 587; κ 10⁷, λ 3 at 10⁻⁶, 37.7% and 1.02; κ 10⁷, λ 3 at 10⁻⁸, 0.0% and 1.00; κ 10⁷, λ 3 at 10⁻¹⁰, 2.4% and 1.74; κ 10⁷, λ 3 at 10⁻¹², 17.5% and 300; κ 10⁵, λ 0.3 at 10⁻⁶, 24.5% and 3.70; κ 10⁵, λ 0.3 at 10⁻⁸, 20.3% and 131; κ 10⁵, λ 0.3 at 10⁻¹⁰, 2.4% and 1.69; κ 10⁵, λ 0.3 at 10⁻¹², 19.8% and 374; κ 10⁵, λ 30 at 10⁻⁶, 28.4% and 374; κ 10⁵, λ 30 at 10⁻⁸, 5.5% and 2.92; κ 10⁵, λ 30 at 10⁻¹⁰, 23.8% and 3935; κ 10⁵, λ 30 at 10⁻¹², 10.5% and 44.4.error with floor ÷ withoutsmallest premium1largest premium4.8·10⁴010203040110¹10²10³10⁴10⁵inner iterations saved, per centerror with floor ÷ withoutκ 10⁵, λ 3κ 10³, λ 3κ 10⁷, λ 3κ 10⁵, λ 0.3κ 10⁵, λ 30each dot one problem at one tolerancethe price of the saving is not predictable
Fig. 5 At c = ½, for five problems at four outer tolerances: the share of inner iterations the floor saves, and the forward error with the floor over the error without it.

It is useless. At c = ½, over twenty runs — five problems at tolerances 10−610^{-6}, 10−810^{-8}, 10−1010^{-10} and 10−1210^{-12} — the error with the floor is between 1.00 and 48,000 times the error without it, and the saving between 0.0 and 37.7 per cent. The two do not track each other. On the worst-conditioned problem at 10−610^{-6} the floor saves 37.7 per cent of the inner work and costs nothing at all, a factor of 1.02, because on that problem the forward error is set by the conditioning and the extra inner accuracy cannot improve it. On the best-conditioned problem at 10−1010^{-10} it saves 31.7 per cent and costs a factor of 48,000, because there the unfloored run’s last step lands the iterate to near machine precision and the floored run’s does not. On the standing problem the premium moves from 32 to 2,636 to 23 to 376 as the tolerance goes from 10−610^{-6} to 10−1210^{-12}, not monotonically.

The reason is the one the earlier essay gave for the extra accuracy existing at all, and it is the gap between a residual and an error that a small residual is not a small error measured on a linear system: the unfloored rule solves the last step to a residual set by the ratio of the last two nonlinear residuals, which under quadratic convergence is tiny, and whether that lands the iterate far below the tolerance depends on where the previous step happened to leave it. That is a property of the sequence of residuals on the particular run, not of the problem’s class or the tolerance’s size. A premium that depends on where one iterate happened to fall is a premium no caller can anticipate.

What a caller should do with this

The measurement narrows the earlier essay’s advice. It said the floor is a trade between a residual and an error, and that whether it is a saving depends on which of the two the caller meant. Both halves stand, with two additions.

If the caller meant the residual, the floor is right and its constant should stay well below one. A half is a reasonable choice and a tenth costs little more work; anything at or above one risks a run that never stops. There is no benefit to tuning between a tenth and a half beyond a few per cent of inner work, and the whole of the risk is on one side.

If the caller meant the error, the floor should not be there, and no constant repairs it. The forward error it costs is proportional to c, so a smaller constant costs less, but how much less depends on the run and cannot be predicted: at c = 0.01 the standing problem at 10−810^{-8} still loses a factor of 44. A caller who wants a forward error should ask for one, which means either a tolerance on the step size, as the accuracy that is thrown away measured for the inner solves, or a residual tolerance divided by an estimate of the condition number — the amplification the condition number is an amplifier measures — the floor from a forward target the earlier essay proposed and nobody has measured.

Where the rule’s other safeguard stands

The forcing rule a tolerance that reads its own residual described has two safeguards, and this measurement touches only one. The other stops the forcing term from falling faster than the residuals justify: if the previous η was not small, the new one may not be much smaller. It governs the early steps, where the floor is inactive; the floor acts only at the end, where the ratio rule asks for a tiny forcing term. On these problems the two act at different ends of the run, which is why every run here with c at or below one takes the same number of outer steps as the unfloored run, and the cliff is entirely the floor’s.

It is worth noticing that the second safeguard’s constant has a meaning the first’s does not. The first safeguard’s constants are Eisenstat and Walker’s, fitted to make the rule converge well on test problems. The floor’s constant is a ratio between two tolerances in the same units, and one is the only value at which it changes kind. That makes it the rarer sort of tuning parameter: one with a region that is safe for a reason, a boundary that can be stated, and a default that is safe by a factor of two.

What this does not settle

One family of nonlinear problems — a symmetric positive definite matrix plus a cubic diagonal term — at 200 unknowns, conjugate gradients as the inner solver, and the second of Eisenstat and Walker’s two forcing rules. A problem whose Newton iteration converges more slowly than quadratically near the root would reach the last step with a larger forcing term and give the floor less to do; the cliff at one should survive, since it is an inequality between the floor and the test, but where the premium lies would move. Each of the twenty premiums is one run on one problem; a seeded family of right-hand sides would turn each into a distribution, and the spread measured across problems here says that distribution would be wide, but not how wide.

The cap of eighty outer steps is a choice. With no cap, some of the stalled runs would eventually creep below the threshold, since each conjugate-gradients solve overshoots its tolerance by a random amount; the measurement shows that the crawl, when it happens, takes more steps than the whole of a converging run, which is the practical meaning of a cliff.

Still open: a floor from a forward target, and the same line in the first forcing rule

The floor a forward target implies. If the caller wants the forward error below some δ, the last step’s relative residual should be about δ divided by the condition number, and the condition number can be estimated from quantities the Krylov solves already produce. A floor set that way would give up only the accuracy the caller said they did not want, and the measurement is what it costs against the unfloored run on the five problems here — and whether a Lanczos estimate of the condition number, which conjugate gradients carries for free, is good enough to set it.

Eisenstat and Walker’s first rule. Their first choice of forcing term is built from the difference between the new residual and the linear model’s prediction of it, not from a ratio of norms. It has no published floor either. Whether it produces the same late over-solving that the floor removes, and whether a floor on it has the same cliff at one, is the comparison that would say whether the line is a property of one rule or of the idea of an adaptive forcing term.

Where this goes next

what one line doesinner work saved, worst case0.09best case0.27forward error cost, worst263610⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴outer toleranceforward errorerror, with the floorerror, without itinner work, rescaledthe grey diagonal is the residual the test asked forboth runs meet it and one is far more accurate One line that buys a quarter of the run The adaptive forcing rule has a floor on it that no published statement of the rule carries: do not solve a step to an accuracy the outer loop will not use. Removing it costs 9 to 27 per cent of the whole inner run. Keeping it costs between 23 and 2,600 times the forward error — accuracy the residual test never asked for and both runs satisfy the test either way. The line is a trade between a residual and an error, and which of the two the caller meant decides whether it is a saving. 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 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. 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.

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 gradientsForcing termForward errorInexact newtonNewton iterationQuadratic convergenceResidualStopping criterion