Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Sequence of solves — the series

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

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

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

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

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

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

    part 6 · sequence

All series