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

What a rebuild is worth

One sequence, one drift, one preconditioner — and six different right answers, because the cheapest rebuild period depends on what a rebuild cost to build and on nothing else. The optimum walks from every member to every twelfth as the setup gets dearer, and the free rule that reads the iteration count beats it in the middle of that range and loses at both ends.
28 min read 24 figures Where the algebra stops being the arithmeticMeasured, not assertedWhose fault is itAssertions that reject

Worth reading first: A factorisation kept past its date · Changing the condition number on purpose · The problem that arrives again.

Two essays in this field have measured how fast an object ages. Neither of them has said what the ageing is worth, and it turns out that the ageing is the smaller half of the question.

Here is the whole of the other half. Reusing a preconditioner saves a rebuild and costs extra iterations. Whether that is a good trade depends on how many iterations one rebuild is worth, and that number is a property of the code rather than of the matrix: it is different for a dense Cholesky, an incomplete factorisation, a multigrid hierarchy and a fill-reducing ordering with a symbolic phase, and it can differ between them by two orders of magnitude on the same problem.

So the same sequence has several right answers, one per object, and none of them is discoverable from the sequence.

The cheapest rebuild period for one drifting sequence, against what a rebuild costsOne sequence, one drift rate, one preconditioner — and six answers, because the answer is not a property of the sequence. Costed in iteration-equivalents, the optimal period runs from every 1 member at a setup worth 5 iterations to every 12 at a setup worth 200. A dense Cholesky at this size is worth 6.7 iterations, which is at the left of the axis, so for it the answer is always to rebuild. The rule that rebuilds when a solve takes 1.5 times what the last fresh one did beats the best fixed period at 1 of the 6 ratios and loses at the rest, because it cannot see the setup cost at all.10¹10²10³03691215what one rebuild is worth, in preconditioned iterationscheapest number of members between rebuildsa dense Cholesky here is worth 6.7 iterationsringed: where the growth rule beats every fixed periodcheapest period, by setup costsetup worth 51setup worth 102setup worth 203setup worth 506setup worth 1008setup worth 20012how long to keep itis a question about what it cost to build
Fig. 1 The cheapest rebuild period for one drifting sequence, against what one rebuild is worth in preconditioned iterations. Everything else is held fixed.

The currency

Every reuse decision is a ratio, so the honest thing to do is to make the ratio the axis rather than bury it in a flop model.

A sequence is costed here in iteration-equivalents: the total number of preconditioned conjugate gradient iterations, plus the number of rebuilds times a setup ratio. The ratio is what one rebuild costs in units of one iteration, and for the objects a real code holds it runs over a wide range:

  • a dense Cholesky at n = 80 is n³/3 against 4n² a step, which is n/12 — 6.7 iterations;
  • an incomplete factorisation of a sparse operator is a few matrix passes, so a handful;
  • a multigrid hierarchy — coarsening, interpolation operators, coarse-grid assembly — is tens;
  • an ordering with a symbolic phase, on a distributed machine where it also decides which processor holds what, can be hundreds.

The measurement is the same twenty-four-member sequence, walked at eight fixed rebuild periods and four growth rules, and then costed at each of six setup ratios. Nothing about the sequence changes between the columns. Only the exchange rate does.

Stored entries per row at each level, 400 unknowns and 1192 edgesA rising curve of stored entries per row against level in the hierarchy, beside a flat one for a geometric hierarchy on a grid.01234567110¹10²levelstored entries per rowalgebraicgeometrictwo complexities, one hierarchygrid complexity3.1operator complexity18geometric, for comparison1.5a ring plus random chords — nothing is anywherelevel 6 is 100% dense
Fig. 2 One of the expensive objects, priced in the field that built it: a multigrid hierarchy, whose setup is a real fraction of a solve rather than a rounding.
Entries in U, against the bound the symbolic phase can compute, on the 5×5 gridA row of horizontal bars. The topmost is longest and is labelled as the bound; every measured bar below it is shorter.the bound211no pivoting127τ = 0.00198τ = 0.003100τ = 0.01106τ = 0.03111τ = 0.1116τ = 0.3117τ = 1138entries in Ua bound, and its slackthe bound, from the graph alone211the worst that occurs138loose by1.5no arithmetic was done to compute the bound — only the pattern of AᵀA and its elimination graphGeorge and Ng: U fits inside chol(AᵀA), whatever the swapsprovable, cheap, and loose
Fig. 3 And the other one: a symbolic phase, which is where the cost of a sparse factorisation lives and which a reuse decision is usually about.

Six answers

a rebuild is worth cheapest period its cost never rebuild rebuild every member
5 iterations every member 170 1,161 170
10 every 2 259 1,166 290
20 every 3 356 1,176 530
50 every 6 542 1,206 1,250
100 every 8 727 1,256 2,450
200 every 12 1,008 1,356 4,850

The optimum walks steadily from one to twelve. At the cheap end, rebuilding at every member is correct and there is no interesting decision to make — which is worth knowing, because it means the dense Cholesky of the previous essays, at 6.7, sits in the regime where the answer is always to rebuild and the reuse question does not arise.

At the expensive end the decision is worth a factor of nearly five: 1,008 against 4,850 for rebuilding every time. And never rebuilding at all is between four and seven times worse than the optimum at every ratio in the table, which is the other thing the figure says — the ageing is real, and no setup cost in this range makes ignoring it correct.

The cheapest rebuild period for one drifting sequence, against what a rebuild costsOne sequence, one drift rate, one preconditioner — and six answers, because the answer is not a property of the sequence. Costed in iteration-equivalents, the optimal period runs from every 1 member at a setup worth 5 iterations to every 12 at a setup worth 200. A dense Cholesky at this size is worth 6.7 iterations, which is at the left of the axis, so for it the answer is always to rebuild. The rule that rebuilds when a solve takes 1.5 times what the last fresh one did beats the best fixed period at 0 of the 6 ratios and loses at the rest, because it cannot see the setup cost at all.10¹10²10³03691215what one rebuild is worth, in preconditioned iterationscheapest number of members between rebuildsa dense Cholesky here is worth 6.7 iterationsringed: where the growth rule beats every fixed periodcheapest period, by setup costsetup worth 51setup worth 102setup worth 204setup worth 506setup worth 10012setup worth 20012how long to keep itis a question about what it cost to build
Fig. 4 The same figure on a sequence that drifts ten times more slowly, where the whole staircase lifts: every object is worth keeping longer, and the shape of the argument does not change.
The cheapest rebuild period for one drifting sequence, against what a rebuild costsOne sequence, one drift rate, one preconditioner — and six answers, because the answer is not a property of the sequence. Costed in iteration-equivalents, the optimal period runs from every 1 member at a setup worth 5 iterations to every 8 at a setup worth 200. A dense Cholesky at this size is worth 6.7 iterations, which is at the left of the axis, so for it the answer is always to rebuild. The rule that rebuilds when a solve takes 1.5 times what the last fresh one did beats the best fixed period at 0 of the 6 ratios and loses at the rest, because it cannot see the setup cost at all.10¹10²10³0246810what one rebuild is worth, in preconditioned iterationscheapest number of members between rebuildsa dense Cholesky here is worth 6.7 iterationsringed: where the growth rule beats every fixed periodcheapest period, by setup costsetup worth 51setup worth 102setup worth 203setup worth 504setup worth 1006setup worth 2008how long to keep itis a question about what it cost to build
Fig. 5 And on one that drifts ten times faster, where it flattens towards rebuilding at every member.

The free rule, and where it stops

The previous essays each found a rule that reads something the iteration already computed and beats every constant. The obvious rule here is the same shape: rebuild when a solve takes more than γ times what the first solve after the last rebuild took. It needs no drift rate, no norm, no eigenvalues, and the quantity it reads is a count the loop already has.

At γ = 1.5 it rebuilds four times over the twenty-four members. Costed:

setup worth growth rule best fixed period which wins
5 328 170 fixed, by 93%
10 348 259 fixed, by 34%
20 388 356 fixed, by 9%
50 508 542 the rule, by 6%
100 708 727 the rule, by 3%
200 1,108 1,008 fixed, by 10%

It wins in the middle and loses at both ends, and the reason is one line: it rebuilds four times whatever a rebuild costs. The number of rebuilds it chooses is a function of the ageing alone, because the ageing is all it can see. At a setup worth 5 the right answer is twenty-four rebuilds and it does four; at a setup worth 200 the right answer is two and it does four.

The cost of a drifting sequence of nonlinear solves, against how often the Jacobian is refactorisedTwenty members, each warm-started from the last, each solved by a chord iteration on a factorisation that may be several members old. Refactorising at every member costs 16.42 MFlop; refactorising every 5 costs 9.27. Past a period of 20 the chord iteration stops converging altogether, which is drawn as an open circle on the ceiling rather than omitted. The filled square is the rule that refactorises when the observed contraction ratio exceeds 0.2: 4 factorisations, 9.22 MFlop, and it was never told the drift rate.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
Fig. 6 The rule that does not have this problem, from the essay on a kept factorisation. There the cliff makes the decision for it, and the setup cost never becomes the binding constraint.
Total inner iterations for a whole inexact Newton solve, against the constant forcing termEvery point is a complete solve of the same problem to the same outer tolerance of 10^-10. At η = 10⁻¹⁴ it takes 9358 conjugate gradient iterations across 9 Newton steps; at η = 0.1 it takes 980 across 10. The left arm is oversolving and the right arm is too many outer steps. The open circle is the adaptive rule, which is not a constant: it costs 1009 iterations and reaches 3.37·10⁻¹¹.10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110²10³10⁴10⁵constant forcing term ηtotal inner iterationsthe adaptive ruleoversolvingstarving the outer loopone problem, twelve budgetsη = 10⁻¹⁴, inner iterations9358cheapest constant0.1its inner iterations980adaptive rule, iterations1009adaptive final residual3.4·10⁻¹¹outer tolerance asked for10⁻¹⁰a tolerance is a cost decisionand its optimum is not machine precision
Fig. 7 And the first rule in this field, where the same objection does not arise because there is nothing to build: a tolerance costs nothing to set.

Why this is worth saying rather than fixing

The obvious repair is to tell the rule the setup ratio. That is correct and it is also the end of the interesting part, because a rule that has been told the setup ratio is a rule with a tuned constant in it, and this field has spent three essays on why a tuned constant is the thing to avoid.

What is worth carrying instead is the shape of the failure, because it is general.

A free measurement is free because something else is paying for it. The residual ratio in a Newton iteration is free because the iteration computes residuals; it happens to be the exact quantity the tolerance decision needs, and that is luck rather than design. The contraction ratio of a chord iteration is free for the same reason and is again exactly right, because the decision there is “is this factorisation still working” and the ratio is the answer.

The iteration count of a preconditioned solve is free too, and it is only half of what the decision needs. The other half — what a rebuild costs — is not a quantity any solve produces, is not visible in any residual, and does not appear anywhere in the iteration. No amount of watching the iteration more carefully will reveal it.

So the field’s reading, stated three essays ago, has a boundary and this is it: a rule that recomputes its decision from what the iteration is doing beats a constant when the decision is entirely about what the iteration is doing. Here it is half about the code, and the rule is half right.

Products with A to return all 2 copies, against the block widthOne bar per block width. Widths below 2 return fewer copies than the eigenvalue has, at every step count up to a basis of half the problem's dimension, and are marked rather than drawn. The cheapest width that works is 2, at 32 products with A; the widest drawn costs 84.an eigenvalue repeated 2 times, in a 200-dimensional problemblock of 1never returns them allblock of 232 products, 16 stepsblock of 351 products, 17 stepsblock of 460 products, 15 stepsblock of 570 products, 14 stepsblock of 684 products, 14 stepsthe narrowest that workscheapest width2its products with A32the widest drawn84narrower than the multiplicity is not slowit is absent
Fig. 8 A cost that is a property of the machine rather than of the matrix, from the field about where the flop count stopped predicting the time. A setup ratio is the same kind of quantity, and it is not visible from inside a solve either.
The same arithmetic, twice, with M = 64 words of fast memoryThree counters against the matrix size on logarithmic axes. The operation count is one curve, because both orderings perform exactly the same operations — 338,120 of them at n = 80. The words moved between fast and slow memory are two curves a factor of 3.49 apart. The factorisations they produce are identical to the last bit.10²10³10⁴10⁵matrix size ncountoperations, bothwords, unblockedwords, blocked (b = 4)the answer does not move‖PA − LU‖/‖A‖, unblocked2.8·10⁻¹⁶‖PA − LU‖/‖A‖, blocked2.8·10⁻¹⁶difference between them0the dashed curve is both orderings' operation countthe solid pair is what they cost
Fig. 9 And the standing reminder that arithmetic is not what a computation spends. A rebuild’s cost lives in that gap, which is exactly why a rule written in iterations cannot see it.

Never rebuilding is the worst policy at every ratio

One column of the table deserves more attention than it usually gets, because it contradicts the way this decision is normally discussed.

The “never rebuild” column runs 1,161, 1,166, 1,176, 1,206, 1,256, 1,356 — barely moving, because a policy with one rebuild in it barely notices what a rebuild costs. And it is between four and seven times the optimum at every single ratio.

That is worth stating plainly because the usual framing of preconditioner reuse is how long it can be kept before something breaks, as though keeping it were the default and rebuilding were the expense. On this measurement the default is wrong. The sequence drifts, the iteration count climbs from 18 to 52, and a policy that never pays for a rebuild pays for it in iterations several times over — even when a rebuild is worth two hundred of them.

There is a regime where never rebuilding is correct, and the last section of this essay is about it. It is the regime where the sequence barely drifts, and the honest summary of the whole table is that both defaults are wrong most of the time and the decision is a measurement.

Incomplete Cholesky on the 10×10 grid: κ 48.4 → 5.12A semi-logarithmic plot of relative residual against iteration for conjugate gradients with and without an incomplete Cholesky preconditioner, the preconditioned curve falling faster.051015202530354010⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹iteration‖r‖ / ‖b‖plain CGIC(0) CGwhat the preconditioner didκ(A)48κ(L⁻¹AL⁻ᵀ)5.1‖A − LLᵀ‖/‖A‖0.0832D Laplacian, n = 100√κ ratio predicts 3.07×
Fig. 10 What a preconditioner does to a spectrum, from the field that established it. Everything above is about how long that picture stays true.
What one weighted Jacobi sweep does to each mode, at ω = 0.67A curve of the damping factor against mode frequency, falling from one at the left through zero and towards minus one at the right. The right-hand half of the plot is shaded, and two horizontal lines mark the worst damping inside it.00.250.50.751-1-0.500.51mode frequency θ / πdamping factor per sweeppredicted±0.333measureda coarse grid seestwo routes to one factorsmoothing factor, scanned0.33smoothing factor, closed form0.33worst mode disagreement3.3·10⁻¹⁶63 interior points, one sweepthe left-hand end is what the coarse grid is for
Fig. 11 And the same question for a smoother, whose setup is cheap and whose staleness is therefore never worth thinking about — the left column of the table, where the answer is always to rebuild.

Two rules, two objects, two outcomes

It is worth putting this essay’s rule beside the one from the essay on a kept factorisation, because they are the same idea and only one of them works.

Both read a quantity the iteration produces for free. Both avoid a tuned constant. Both are scale-free. The chord rule wins at every drift rate measured; the growth rule wins at two setup ratios out of six.

The difference is not the quality of the rule, it is the shape of the failure it is guarding against. A stale factorisation stops working, and a rule that watches for it not working is watching the right thing: the cost of being wrong is unbounded on one side and small on the other, so the rule only has to detect the cliff. A stale preconditioner costs more, symmetrically, and detecting that it costs more is only half of a comparison whose other half is off-stage.

A rule can be free and right when the decision is one-sided. When both directions cost, the rule needs both prices, and a free measurement gives it one.

The cost of a drifting sequence of nonlinear solves, against how often the Jacobian is refactorisedTwenty members, each warm-started from the last, each solved by a chord iteration on a factorisation that may be several members old. Refactorising at every member costs 19.01 MFlop; refactorising every 3 costs 14.50. Past a period of 6 the chord iteration stops converging altogether, which is drawn as an open circle on the ceiling rather than omitted. The filled square is the rule that refactorises when the observed contraction ratio exceeds 0.2: 8 factorisations, 12.33 MFlop, and it was never told the drift rate.024681012141618202210⁶10⁷10⁸members served by one factorisationmultiplications for the whole sequencedoes not convergethe contraction ruledrift 0.032 a memberevery member1.9·10⁷every 3 members1.5·10⁷contraction rule1.2·10⁷its factorisations8cliff at a period of6a factorisation has a shelf lifeand the cliff is past the optimum
Fig. 12 The one-sided decision, drawn at the drift where it is sharpest: the cliff is one member past the optimum and the rule only has to notice it.
An incomplete Cholesky kept while the operator turns anisotropic, against one rebuilt at every memberThe five-point operator's two directions stop being equally weighted, ε running from 1 down to 0.0331, with the sparsity pattern unchanged throughout — so the factorisation from the first member stays applicable for the whole run, which is the situation in which it gets kept. The kept one goes from 21 iterations to 54. The rebuilt one goes from 21 to 16, because an anisotropic operator is an easier problem for a factorisation that knows about the anisotropy. The two start at the same point by construction and never meet again.024681012141618200102030405060member of the sequencepreconditioned conjugate gradient iterationskept from the first memberrebuilt every memberone operator, two policieskept, first member21kept, last member54rebuilt, first member21rebuilt, last member16ε at the last member0.033the problem got easierand the kept preconditioner got worse at it
Fig. 13 And the two-sided one, where nothing ever fails and the whole question is a price.

The sequence that needs no rule

There is one more case and it is worth drawing, because it is the regime most sequences are actually in and because the rule is wrong there too.

Slow the drift down by four orders of magnitude and the preconditioner never goes stale: one build serves all twenty-four members, never rebuilding is the cheapest fixed policy at every setup ratio, and every rebuild is pure waste.

The growth rule still rebuilds twice. Not because it detected ageing — there is none — but because the iteration count moves with the right-hand side. Two solves of the same matrix to the same tolerance take different numbers of steps depending on where b lands in the spectrum, and a rule watching that count cannot tell the variation from the ageing.

That is a third way to be fooled, and it is the one most likely to bite in practice, because the right-hand sides in a real sequence are not drawn from one distribution either.

Conjugate gradients at κ = 104, against the bound κ permitsA semi-logarithmic plot of the relative A-norm error against iteration count. The measured curve falls below a smooth dashed curve showing the classical condition-number bound.0408012016020024010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration‖e‖_A / ‖e₀‖_Ameasuredκ bound119 steps40×40, spectrum spread evenly in logbound permits 1417
Fig. 14 Why the count moves at all: the conjugate gradient rate is a bound over a spectrum, and where a particular right-hand side sits in that spectrum decides where inside the bound the run lands.
The spectrum of C⁻¹T against T's own, n = 64, ρ = 0.8Two sorted spectra on a linear vertical axis. The unpreconditioned Toeplitz matrix spreads its eigenvalues across its whole range; the preconditioned operator puts 97% of them within a tenth of 1, with 0 below zero.08162432404856640123456789index, sortedeigenvalueT aloneC⁻¹Teigenvalues, not singular valuesfraction within 0.1 of 10.97eigenvalues below zero0λ_min of the preconditioner0.11the dashed line is 1, where the cluster formsthe solid line is zero
Fig. 15 And the spread that variation comes out of. The same matrix, solved twice, need not take the same number of steps — which is a fact about Krylov methods and a nuisance for anything that watches them.

Reading the table for a real code

The figure is a staircase over a synthetic ratio, and it is worth saying how somebody with an actual solver would use it, because the answer is not to read a period off the chart.

The ratio is measurable directly and cheaply: time one rebuild, time one preconditioned iteration, and divide. That is two measurements a profiler already has, and it is the only site-specific number the whole decision needs. Everything else on the figure — how fast the sequence drifts, how many members there are — is a property of the problem being solved rather than of the code, and the figure shows that the answer moves far more with the ratio than with either of those.

Two consequences follow that are worth stating separately from the measurement.

The right period is not portable between codes. The same sequence solved by two solvers with different setup costs has two different right answers, and a number carried across from one to the other is wrong by however far apart their ratios are — which the table puts at a factor of five in total cost at the extremes.

And it is not portable between machines. The ratio is a ratio of two timings, and the two scale differently: a setup that is largely symbolic and serial does not accelerate the way an iteration made of matrix–vector products does. A period tuned on one machine is a period tuned for that machine’s ratio, and this collection’s cost field has spent an entire run establishing that such numbers do not travel.

What is asserted

Four things, each with a case it must refuse.

That the optimum never falls as the setup gets more expensive — one, two, three, six, eight, twelve — and that it moves from rebuilding at every member to rebuilding once in twelve across the range measured.

That never rebuilding is several times worse than the optimum at every ratio, so the essay is not an argument for keeping things.

That the growth rule beats the best fixed period at 50 and 100 and loses at 5 and 200, which is the refusal: fed the claim that it wins everywhere, the assertion fails.

And that on a sequence with essentially no drift, the rule rebuilds anyway — which is asserted in the direction that says the rule is fooled rather than in the direction that says it agrees.

The cheapest rebuild period for one drifting sequence, against what a rebuild costsOne sequence, one drift rate, one preconditioner — and six answers, because the answer is not a property of the sequence. Costed in iteration-equivalents, the optimal period runs from every 1 member at a setup worth 5 iterations to every 12 at a setup worth 200. A dense Cholesky at this size is worth 6.7 iterations, which is at the left of the axis, so for it the answer is always to rebuild. The rule that rebuilds when a solve takes 1.5 times what the last fresh one did beats the best fixed period at 1 of the 6 ratios and loses at the rest, because it cannot see the setup cost at all.10¹10²10³03691215what one rebuild is worth, in preconditioned iterationscheapest number of members between rebuildsa dense Cholesky here is worth 6.7 iterationsringed: where the growth rule beats every fixed periodcheapest period, by setup costsetup worth 51setup worth 102setup worth 203setup worth 506setup worth 1008setup worth 20012how long to keep itis a question about what it cost to build
Fig. 16 A drift between the two extremes, where the staircase is at its steepest and the decision is worth the most.
The cheapest rebuild period for one drifting sequence, against what a rebuild costsOne sequence, one drift rate, one preconditioner — and six answers, because the answer is not a property of the sequence. Costed in iteration-equivalents, the optimal period runs from every 1 member at a setup worth 5 iterations to every 8 at a setup worth 200. A dense Cholesky at this size is worth 6.7 iterations, which is at the left of the axis, so for it the answer is always to rebuild. The rule that rebuilds when a solve takes 1.5 times what the last fresh one did beats the best fixed period at 0 of the 6 ratios and loses at the rest, because it cannot see the setup cost at all.10¹10²10³0246810what one rebuild is worth, in preconditioned iterationscheapest number of members between rebuildsa dense Cholesky here is worth 6.7 iterationsringed: where the growth rule beats every fixed periodcheapest period, by setup costsetup worth 51setup worth 102setup worth 203setup worth 504setup worth 1006setup worth 2008how long to keep itis a question about what it cost to build
Fig. 17 And another, for the same reason: the walk is a robust feature of the measurement rather than something one drift rate produces.
An incomplete Cholesky kept while the operator turns anisotropic, against one rebuilt at every memberThe five-point operator's two directions stop being equally weighted, ε running from 1 down to 0.0331, with the sparsity pattern unchanged throughout — so the factorisation from the first member stays applicable for the whole run, which is the situation in which it gets kept. The kept one goes from 18 iterations to 52. The rebuilt one goes from 18 to 13, because an anisotropic operator is an easier problem for a factorisation that knows about the anisotropy. The two start at the same point by construction and never meet again.0246810121416182001020304050member of the sequencepreconditioned conjugate gradient iterationskept from the first memberrebuilt every memberone operator, two policieskept, first member18kept, last member52rebuilt, first member18rebuilt, last member13ε at the last member0.033the problem got easierand the kept preconditioner got worse at it
Fig. 18 The ageing itself, which this essay prices and the previous one measured.
Preconditioned iterations against the size of the drift, for a drift on each half of the spectrumThe preconditioner is the exact Cholesky factorisation of the first matrix, so it solves that matrix in one step and every iteration counted here is bought by the drift. Both curves are drifts of the same relative Frobenius norm; the upper one sits on the half of the spectrum with the small eigenvalues and the lower on the half with the large. At a relative drift of 10⁻² they cost 38 and 9 iterations, because the drift is divided by the eigenvalue it lands on: the preconditioned matrix has eigenvalues 1 + w/λ, and λ runs over 10⁴.10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹10112233445566relative drift ‖E‖ / ‖A₀‖preconditioned conjugate gradient iterationson the small eigenvalueson the large onessame drift, two placessmall end at 10⁻²38large end at 10⁻²9κ(M⁻¹A), small end36κ(M⁻¹A), large end1.3‖E‖/‖A₀‖, both0.01how much the matrix changedis not what the preconditioner cares about
Fig. 19 And what governs it, which is where the drift landed rather than how large it was.
What 24 members of a sequence cost, by what changes between themEvery bar is 24 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 — 12.7 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: 7 factorisations for 24 members. When everything changes, nothing carries.nothing4.2%the right-hand side12.7%the matrix, slowly83.2%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 24 members cost in factorisationssame: factorisations1rhs: factorisations1drift: factorisations7independent: factorisations24what changes between the membersdecides what may be carried
Fig. 20 Where this sits in the field’s ledger. Every bar in that figure has a setup ratio hidden inside it, and this essay is what happens when it is pulled out and made the axis.
Chord steps per member of a drifting sequence, with the factorisation rebuilt every 4Each point is one member of a continuation, warm-started from the previous member's answer and solved with a factorisation that is between zero and 3 members old. The lower series is the same sequence with a fresh factorisation at every member, which costs 6 to 5 steps throughout. The kept run costs 6 steps on a fresh factor and 12 at its worst, for 5 factorisations against 20.03691215182103691215member of the sequencechord steps to reach the tolerancea fresh factorisation each memberthe ringed points are the refactorisationsrebuilt every 4factorisations5chord steps160worst member's steps12multiplications1.2·10⁷with a fresh factor each time1.8·10⁷a factor is cheapest the member it was built forand dearest the member before it is replaced
Fig. 21 The sawtooth one object down, whose optimum is a period for the same reason and whose failure is a cliff rather than a slope.
LSQR steps to a normal residual of 10⁻¹², with and without a sketched preconditionerTwo curves against κ(A). The unpreconditioned solve takes 15, 22, 32, 59, 150 steps as the conditioning worsens, and at the worst one it does not reach the tolerance inside 150. The preconditioned solve takes 10, 10, 10, 10, 10 — flat across eight decades. Both return the same vector, to the accuracy the problem allows: the preconditioned answer and the direct one differ by about κ(A)·u at every κ, 5.7·10⁻⁶ at the worst. The SAME sketch used as an answer instead of as a preconditioner is 4.5 away.10²10⁴10⁶10⁸10¹⁰110¹10²10³condition number of the matrixLSQR steps to 10⁻¹²no preconditionersketchedthe cost, not the answersteps, preconditioned10steps, without150answer gap, preconditioned5.7·10⁻⁶κ(A)·u at the worst κ1.1·10⁻⁶answer gap, sketch-and-solve4.5one sketch, two things to do with itand only one of them moves the answer
Fig. 22 And the iteration count itself, which is the currency everything here is priced in and half of what the decision needs.
Convergence factor against grid size, with 2 pre-smoothing sweepsThree curves against grid size on a logarithmic horizontal axis. Two rise towards one; the third is a flat line near a tenth.10¹10¹.³10¹.⁶10¹.⁹⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰¹10².²00.250.50.751grid points nresidual reduction per stepJacobiGauss–SeidelV-cycleV-cycle spread, 8× in size0.003Jacobi at n = 1270.99work exponent, fitted0.079the dashed curve is cos(πh), Jacobi's closed formthe flat line is the whole method
Fig. 23 The convergence rate of the most expensive object in the table, from the field that built it. Its setup is what makes the right-hand columns of this essay’s figure the interesting ones.
Nonzeros in the Cholesky factor of the 8×8 grid Laplacian, by orderingA horizontal bar chart comparing the number of nonzero entries in the Cholesky factor under four elimination orderings, with reference marks for the matrix itself and for a dense factor.natural519reverse Cuthill–McKee428minimum degree359nested dissection434matrix: 176 entries · dense factor: 2080bandwidth 8 · 2.95× the matrixbandwidth 8 · 2.43× the matrixbandwidth 49 · 2.04× the matrixbandwidth 48 · 2.47× the matrixn = 64, five-point stencilevery ordering fills in; none avoids it
Fig. 24 And the other one: the orderings whose symbolic phase is what a reuse decision is usually protecting.

Where this goes next

10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹10112233445566relative drift ‖E‖ / ‖A₀‖preconditioned conjugate gradient iterationson the small eigenvalueson the large onessame drift, two placessmall end at 10⁻²38large end at 10⁻²9κ(M⁻¹A), small end36κ(M⁻¹A), large end1.3‖E‖/‖A₀‖, both0.01how much the matrix changedis not what the preconditioner cares about Where the drift lands The standing rule for when a preconditioner has gone stale is to rebuild it once the matrix has changed by more than some fraction of itself. Two drifts of exactly the same relative size cost 19 iterations and 5 on the same matrix, and the quantity that separates them is not in the rule at all — the perturbation is divided by the eigenvalue it lands on. 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. 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.

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.

Cholesky factorisationCondition numberConjugate gradientsFlop countIncomplete factorisationMultigridPreconditioningStopping criterionWarm start