Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Newton iteration — where it appears

Solving a nonlinear equation by repeatedly linearising it, which converges quadratically once it is close and halves its error before that. It converges quadratically once close and unpredictably before that, and the accuracy of its inner solve turns out to be worth far less than the theory suggests.

Named by 18 essays across 6 fields — each of them below, with the objects they name alongside it.

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.

sequence · Sequence of solves 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.

sequence · Inexact newton 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.

sequence · Inexact newton 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

A factorisation kept past its date

One Cholesky factor can serve five members of a drifting sequence and save 44 per cent of the work. Kept for twenty it does not lose accuracy — it stops converging altogether. The optimum and the cliff are four members apart, both move with the drift, and a rule written in a ratio the iteration has already computed finds them without being told what the drift is.

sequence · Reuse 159131721252910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹steprelative error in the orthogonal factorNewtonNewton, scaledNewton–Schulzone fixed point, three costsscaled Newton, steps7Newton–Schulz, steps28Newton at step 657scaled Newton at step 64.4·10⁻¹³a Newton step needs an inverseand a Schulz step needs two products

An iteration that only multiplies

Newton's iteration for the polar factor needs an inverse every step. Newton–Schulz needs only matrix products — nothing that reads an entry, nothing that pivots — and it converges if and only if every singular value is below √3. At 1.73205 it converges and at 1.73206 it returns an orthogonal matrix that is not the answer, with a residual of 5·10⁻¹⁶ and nothing to say so.

orthogonality · Polar decomposition -2-101234-5-3-1135real partimaginary part4 insidea countable spectruminside the contour4drawn12existing∞worst branch residual1.6·10⁻¹⁵there is no last eigenvalueso the question has to change

A problem with infinitely many eigenvalues

Let the matrix depend on λ through something that is not a polynomial and three things stop being true at once. There is no linearisation, there is no characteristic polynomial, and "compute the spectrum" is not a request that can be granted — the only finite question is how many eigenvalues are inside this circle.

polynomial · Nonlinear eigenvalue 0246810121410⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹interior-point iterationrelative error, and μcertified from iterate 1μthe iterate's errorthe crossover's errorone solve, checkediterations15first certified iterate1iterate error there0.22crossover error there4·10⁻¹⁴the active set arrives long before the digitsand a crossover collects them at once

The active set before the digits

An interior-point method takes fifteen iterations on a quadratic programme with forty constraints, and its iterate has eight correct digits at the eleventh. Take the constraints its diagonal calls active at the first iterate, solve the equality problem they define once, and check the answer against the conditions for optimality. It passes, to thirteen digits. The step's matrix had a condition number of 43 at that iterate, and 7·10¹⁵ at the last.

constraint · Interior-point conditioning 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.

sequence · Sequence of solves 0204060801001share of shufflings, per centarithmetic ÷ the sorted order'sthe sorted order, and the nearest-neighbour paththe order is a free variabledrift between neighbours0.04median penalty1.5worst penalty1.8factorisations, sorted4worst shuffle's16greedy ÷ sorted1the same sixteen problemsat two prices

The order a batch arrives in

Sixteen problems over a parameter, solved in the order the loop produced them, cost a median of 1.54 times what the same sixteen cost sorted, and 2.80 times at the worst shuffling. A nearest-neighbour path computed from the parameter values alone recovers the sorted cost exactly, at every drift and every shuffle.

sequence · Sequence of solves the damagewell scaled, nothing done0.9110^±3, nothing done0.095never certified, of 62at 10^±3rows to unit norm0.64rows by right-hand side0.6start at the rows0.43012300.250.50.751rows rescaled by 10ᵏshare that certifiesnothing donestart at the rowsrows to unit normrows by their right-hand sidethe grey line is a well-scaled programme with nothing doneboth equilibrations are flat, and below it

Two repairs for one symptom

Rescale a quadratic programme's constraint rows over six decades and the crossover that certified its answer at iterate 1.5 first certifies at 69.8, with two of six programmes never certifying at all. Normalising the rows removes the spread completely — the same numbers at 10¹, 10² and 10³ either way. Starting the method at the magnitudes the rows imply repairs the iteration count completely and the identification only halfway. They are two repairs and they fix different halves.

constraint · Interior-point conditioning 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.

sequence · Inexact newton 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.

sequence · Inexact newton 11.522.511.52xyexactly one roota verdict, not a bound‖I − C F′(X)‖0.28width of X0.8width of K(X)0.23strictly inside is a proofand overlapping is nothing at all

Proving the answer is in the box

Every other method here computes a number and estimates how wrong it is. This one returns a verdict: there is exactly one solution in this box, or there is none, or — the honest third outcome — nothing can be said. Two of the three are proofs about infinitely many points from finitely many operations.

arithmetic · Interval 10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶050100150200250relative residual tolerance of every solveinner steps over twenty membersprevious answerline, last twoparabola, last threea straight path, twenty members, drift 0.02tolerance 10⁻⁶: previous answer62tolerance 10⁻⁶: line11tolerance 10⁻⁶: parabola17tolerance 10⁻¹⁰: previous answer160tolerance 10⁻¹⁰: line12tolerance 10⁻¹⁰: parabola14tolerance 10⁻¹⁴: previous answer261tolerance 10⁻¹⁴: line17tolerance 10⁻¹⁴: parabola23tighter to the lefteach point is a whole run of twenty

A straight path has nothing for a parabola to fit

The line through the last two answers beat the parabola through the last three on a drifting sequence, and the reason offered was that the parabola amplifies the stored answers' error. Tightening the solve tolerance from 10⁻⁶ to 10⁻¹⁴ should have reversed that, and it does not: the line needs 7 to 18 inner steps over twenty members at every tolerance and the parabola 14 to 23. The sequence's roots move along a straight line, so the line is exact and there is nothing else to fit. Bend the path by a part in ten thousand and the parabola wins below 10⁻⁹, by 105 steps to 75 at 10⁻¹⁴.

sequence · Sequence of solves 010203040run, by bend then tolerancesteps beyond the better fixed degreestraightbend 10⁻⁵bend 10⁻⁴bend 0.001bend 0.01bend 0.1● second difference ■ residual at both ○ wrong fixed degreethirty runs: steps beyond the better degreesecond difference: runs matching the better degree, of 3026second difference: worst excess, steps5residual at both: runs matching the better degree, of 3029residual at both: extra residuals, in steps4.5wrong fixed degree: worst excess, steps35zero is the better degree, known in advanceeach group of five is one bend

The degree the history chooses

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

sequence · Sequence of solves 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.

sequence · Inexact newton best start, its steps, and the saving over the better interpolanttol 10⁻⁶tol 10⁻⁸tol 10⁻¹⁰tol 10⁻¹²tol 10⁻¹⁴straightL5 4 (−7)L5 6 (−6)L4 8 (−4)L4 9 (−8)L5 12 (−5)bend 10⁻⁵L4 6 (−6)P5 13 (−5)P4 24 (−1)P3 30P3 59bend 10⁻⁴P6 8 (−5)P5 20 (−2)P3 26P3 43P3 75bend 0.001P4 12 (−5)P4 22 (−1)P3 29P3 58P3 93bend 0.01P5 18 (−2)P3 24P3 42P3 73P3 109bend 0.1P4 20 (−1)P3 27P3 58P3 93P3 133a least-squares fit is bestan interpolant is bestL: line, P: parabola, number: answers usedbend: c in c·sin 3t

A fit wins where the steps were few

The line through the last two answers of a sequence of solves amplifies their stored error by √5, and the parabola through the last three by √19. A least-squares line through five amplifies it by 1.05 and a parabola through six by 1.79, and on a straight path both beat their interpolants at every tolerance: 12 inner steps against 17 at 10⁻¹⁴. On a bent path they lose, by exactly the ratio of their truncation constants, and they lose in the runs that cost a hundred steps rather than ten. Over thirty runs no fitted start beats the parabola through three, and the best of eight starts chosen per run saves 58 steps out of 1,212.

sequence · Sequence of solves 10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1εrelative error in J(x)vforwardcentralcancellationtruncationagainst a derivative that is exactforward floor1.3·10⁻¹⁰central floor1.1·10⁻¹²truncation slope, forward1truncation slope, central2no ε reaches the roundoffand the analytic derivative is free of the choice

An operator with no entries

At the sizes where linear algebra is expensive the matrix does not exist. What exists is a subroutine that returns Av. Every Krylov method survives that unchanged; every algorithm that reads an entry disappears. And the derivative such a code computes is accurate to ten digits instead of sixteen, which turns out to cost nothing at all.

iterative · Matrix-free

Named alongside it

The objects these essays reach for when they reach for this one.

Flop countExact ground truthStopping criterionWarm startCholesky factorisationCondition numberConjugate gradientsForcing termInexact newtonQuadratic convergenceExtrapolationKrylov subspace

All concepts