Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Inexact newton — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · sequence
  2. 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.

    part 2 · sequence
  3. total inner iterationscold at η = 1e-107016scaled warm start6837unscaled728910⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10³10³.⁵10⁴forcing term ηinner iterationsthe previous stepstarted at zerothe previous step, scaledthree curves within eight per cent of each otherand the unscaled guess is the worst of the three

    A guess worth two per cent

    The previous Newton step looks like a free guess at the next one, and it is worth nothing. Started from it unscaled, the inner solve costs 4 to 61 per cent more than starting from zero, because the guess is 15 to 209 times too large. Scaled by the ratio of the two residual norms it is the right size and halves the starting residual — which buys a constant handful of inner iterations, not a share, because conjugate gradients costs the logarithm of its tolerance.

    part 3 · sequence
  4. 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.

    part 4 · sequence
  5. 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

    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.

    part 5 · sequence
  6. error ÷ target, nineteen cellsgiven: worst3.5·10⁴known: worst0.017kappa: worst0.058effective: worst0.18oracle: worst0.8510⁻⁵10⁻³10⁻¹10¹10³10⁵forward error ÷ targetδ as the residual toleranceδ/κ(A)δ/κ̂RitzeffectiveRitzoracle stopno floordashed: the targeta residual tolerance is not a forward one

    A target the residual can promise

    A caller who wants inexact Newton's answer to six digits usually passes 10⁻⁶ as the residual tolerance, and on five problems at four targets that misses by 7 to 35,000 times. Divide the target by a condition number and it is met on every cell where a residual can certify it — and the condition number need not be known: the Ritz values conjugate gradients produces on the way give the Jacobian's own, settled by the sixth Newton step and within eleven per cent of the truth at the end, and two to nineteen times below the linear part's. Stopped that way, with the usual floor under the forcing term, the run lands within a fifth of its target and is cheaper on 16 of 19 cells than the unfloored run stopped by someone who knows the answer.

    part 6 · sequence
  7. tolerance ÷ residual reachedfirst choice, model error, unfloored median34second choice, residual ratio, unfloored median95110¹10²10³10⁴tolerance ÷ residual reachedstandingeasyhardmildstrongfirst choicesecond choicegrey: with the floordashed: stopped exactly at the testboth rules over-solve the last step

    Two forcing terms, one floor

    Inexact Newton's adaptive forcing rule comes in two versions, and every measurement of the floor under it used the second, which reads the ratio of the last two residuals. The first reads how wrong the linear model was at the last step, and it was natural to hope that a rule watching the model's own error would not solve its last step past what the stopping test needs. It does. Run without the floor on five problems at four forward targets, it over-solves its last step by a median of 34 times, against the second rule's 95; the floor saves 17.5 per cent of its inner work, against 16.0. Floored, the first rule is the cheaper by 4.6 per cent overall, and it buys that with Newton steps: two more on the median cell, a third less inner work on the strongly nonlinear problem, and 4.5 per cent more on the easy one.

    part 7 · sequence

All series