What 12 members of a sequence cost, by what changes between them
At its defaults it draws what 12 members of a sequence cost, by what changes between them. Every 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.
sequence-cost is one function in lib/figures/sequence.js —
sequences — a solve inside an outer loop, and the accuracy the loop throws away. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
Every 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.
show: "fit-map"
The arguments are the ones A fit wins where the steps were few passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Twenty-member runs at drift 0.02. Lines and parabolas through the fewest answers (L2, P3) or fitted by least squares to more (L3 to L5, P4 to P6). Each cell names the start with the fewest inner steps, its steps, and in brackets the saving over the better of L2 and P3. c = 0: L5 4 (7), L5 6 (6), L4 8 (4), L4 9 (8), L5 12 (5); c = 10⁻⁵: L4 6 (6), P5 13 (5), P4 24 (1), P3 30 (0), P3 59 (0); c = 10⁻⁴: P6 8 (5), P5 20 (2), P3 26 (0), P3 43 (0), P3 75 (0); c = 0.001: P4 12 (5), P4 22 (1), P3 29 (0), P3 58 (0), P3 93 (0); c = 0.01: P5 18 (2), P3 24 (0), P3 42 (0), P3 73 (0), P3 109 (0); c = 0.1: P4 20 (1), P3 27 (0), P3 58 (0), P3 93 (0), P3 133 (0).
show: "fit-trade"
The arguments are the ones A fit wins where the steps were few passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Each point is one fixed combination of the last m stored answers that predicts the next one. Horizontally, the Euclidean norm of its coefficients, which multiplies the error the stored answers carry. Vertically, how far it misses a path that is exactly quadratic (for the lines) or cubic (for the parabolas), in units of that path's second or third difference. line through 2: coefficients 2.00, -1.00, norm 2.24, miss 2.00; line fitted to 3: coefficients 1.33, 0.33, -0.67, norm 1.53, miss 3.33; line fitted to 4: coefficients 1.00, 0.50, 0.00, -0.50, norm 1.22, miss 5.00; line fitted to 5: coefficients 0.80, 0.50, 0.20, -0.10, -0.40, norm 1.05, miss 7.00; parabola through 3: coefficients 3.00, -3.00, 1.00, norm 4.36, miss 6.00; parabola fitted to 4: coefficients 2.25, -0.75, -1.25, 0.75, norm 2.78, miss 10.50; parabola fitted to 5: coefficients 1.80, 0.00, -0.80, -0.60, 0.60, norm 2.14, miss 16.80; parabola fitted to 6: coefficients 1.50, 0.30, -0.40, -0.60, -0.30, 0.50, norm 1.79, miss 25.20.
show: "fit-tolerance", c: 0
The arguments are the ones A fit wins where the steps were few passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The drifting sequence of 120 unknowns, drift 0.02, factorisation rebuilt every four members; roots on a straight line. 10⁻⁶: line through 2 11, line fitted to 5 4, parabola through 3 17, parabola fitted to 6 9; 10⁻⁸: line through 2 12, line fitted to 5 6, parabola through 3 16, parabola fitted to 6 10; 10⁻¹⁰: line through 2 12, line fitted to 5 8, parabola through 3 14, parabola fitted to 6 9; 10⁻¹²: line through 2 17, line fitted to 5 9, parabola through 3 23, parabola fitted to 6 15; 10⁻¹⁴: line through 2 17, line fitted to 5 12, parabola through 3 23, parabola fitted to 6 15.
show: "fit-starts", c: 0.0001, d: 1
The arguments are the ones A fit wins where the steps were few passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The median over members of the relative distance between the start and the member's exact root, on logarithmic axes, with the tolerance itself drawn as a dashed line. 10⁻⁶: line through 2 2.97·10⁻⁶, line fitted to 3 9.84·10⁻⁷, line fitted to 4 1.34·10⁻⁶, line fitted to 5 1.69·10⁻⁶; 10⁻⁸: line through 2 5.09·10⁻⁷, line fitted to 3 8.49·10⁻⁷, line fitted to 4 1.3·10⁻⁶, line fitted to 5 1.73·10⁻⁶; 10⁻¹⁰: line through 2 5.21·10⁻⁷, line fitted to 3 8.73·10⁻⁷, line fitted to 4 1.32·10⁻⁶, line fitted to 5 1.77·10⁻⁶; 10⁻¹²: line through 2 5.19·10⁻⁷, line fitted to 3 8.71·10⁻⁷, line fitted to 4 1.31·10⁻⁶, line fitted to 5 1.77·10⁻⁶; 10⁻¹⁴: line through 2 5.19·10⁻⁷, line fitted to 3 8.71·10⁻⁷, line fitted to 4 1.31·10⁻⁶, line fitted to 5 1.77·10⁻⁶.
show: "fit-tolerance", c: 0.0001
The arguments are the ones A fit wins where the steps were few passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The drifting sequence of 120 unknowns, drift 0.02, factorisation rebuilt every four members; roots on a line bent by 10⁻⁴·sin 3t. 10⁻⁶: line through 2 13, line fitted to 5 21, parabola through 3 17, parabola fitted to 6 8; 10⁻⁸: line through 2 23, line fitted to 5 23, parabola through 3 22, parabola fitted to 6 22; 10⁻¹⁰: line through 2 39, line fitted to 5 44, parabola through 3 26, parabola fitted to 6 28; 10⁻¹²: line through 2 71, line fitted to 5 74, parabola through 3 43, parabola fitted to 6 55; 10⁻¹⁴: line through 2 105, line fitted to 5 115, parabola through 3 75, parabola fitted to 6 92.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
101 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
every start converges at tolerance 0.000001 — checked 9 times
on the straight path the line beats the parabola at 0.000001 — checked 9 times
on the straight path the line starts within a thousand tolerances at 0.000001 — checked 9 times
a nearest-neighbour reordering recovers the sorted cost exactly at seed 1 — checked 8 times
every start converges, line fitted to 5, 0.000001 — checked 5 times
every start converges, line through 2, 0.000001 — checked 5 times
every start converges, parabola fitted to 6, 0.000001 — checked 5 times
every start converges, parabola through 3, 0.000001 — checked 5 times
a linear extrapolation costs fewer inner steps than a warm start at drift 0.01 — checked 4 times
always taking the parabola costs under a fifth of what always taking the line does, beyond the better degree, at drift 0.01 — checked 3 times
every run of the grid converges at drift 0.01 — checked 3 times
a bend no larger than the path itself
a bend the sweep is drawn at: 0 or a power of ten from 10⁻⁵ to 10⁻¹
a coefficient list exactly when the start is a fixed combination of stored answers
a conditioning the SPD construction can hold
a drift the sweep is drawn at
a fitted degree from zero to three
a reading of the sequence this generator draws
a refactorisation period the sweep is drawn at
a refactorisation rule of one kind or the other
a schedule with something in it
a sequence length the four policies are all affordable at
a sequence that changes only its right-hand side is cheaper than one that changes everything
a size the dense factorisations are affordable at
a solve tolerance between rounding and a rough answer
an extrapolation this routine implements
an extrapolation this walk implements
and a drifting matrix costs between the two, or at a short sequence about as much as the independent one
and a quadratic one costs more than the linear
and the linear start is never the first of the three to stop converging
and the order costs something
and the parabola wins most of the bent grid
at least as many stored answers as the fit has coefficients, and at most eight
at the predicted threshold the free rule beats either fixed degree over the grid
choosing by residual picks the better degree on nearly every cell
enough drifts where every start converges
every order solves every member
four kinds of sequence
lines or parabolas
matmul shapes agree
on a bent path the parabola wins at the tightest tolerance
on the bent path at a tight tolerance it stays above it
on the straight path the gap stays below the threshold at every member
the free rule is never worse than the worse degree
the line wins every tolerance on the straight path
the residual rule beats always-the-parabola only if a residual costs under a quarter of a step
the saving is a factor rather than a margin
Against the rule
The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
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.
When the problem arrives againA 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⁻¹⁴.
When the problem arrives againA 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.
When the problem arrives againThe 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.
When the problem arrives againThe 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.
When the problem arrives againThe 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.