The last digit is the cheapest

Every cost curve in this field has the same shape. A direct solve is a fixed price and buys every digit the arithmetic has. An iterative solve buys digits at a constant rate — conjugate gradients takes about the same number of steps for each further factor of ten, which is what the rate the condition number predicts measures. A hierarchical format buys them at a worsening rate: where the format starts paying prices a rank against an accuracy and the rank grows faster than the digits do.

Fixed, constant, or worsening. There is a method here whose curve is none of those.

The measurement #

Counting the eigenvalues inside a circle is an integral of a trace, and the trapezoidal rule on a circle is the right quadrature because the integrand is analytic and periodic. Measured on a four-by-four delay problem, on a circle of radius two containing two eigenvalues:

The third column roughly doubles each time. Each doubling of the work buys about twice as many digits as the previous doubling did, so the price of a digit halves every time it is paid — for as long as it is paid at all, which is four doublings and is measured below.

Sixteen points cost twice eight and buy 0.6 digits. A hundred and twenty-eight cost twice sixty-four and buy 6.4. On any other curve in this field, that ordering runs the other way.

Why it inverts #

The mechanism is one of the pleasant facts of numerical analysis and it is worth stating carefully because it is what limits the finding.

The trapezoidal rule on a non-periodic interval has an error of O(h²), so halving h buys a fixed two digits per four-fold refinement — the algebraic behaviour every quadrature rule has in a first course. On a periodic analytic function the Euler–Maclaurin correction terms all cancel: every one of them involves the difference of derivatives at the two endpoints, and on a closed contour the endpoints are the same point. What is left is not an algebraic term at all but one that decays like ρ⁻ᴺ for a ρ set by how far the integrand can be continued analytically off the contour.

Geometric decay in N, plotted against a doubling N, is what produces the doubling third column. Nothing about the method is clever; the integrand’s analyticity is doing all the work.

What sets ρ, and what it costs when it is small #

ρ is the distance from the contour to the nearest singularity of the integrand, measured in the right conformal sense — and the singularities of tr(T⁻¹T′) are exactly the eigenvalues.

So a circle that runs close to an eigenvalue converges slowly. Measured at radius 1.5, which passes near an eigenvalue at 1.587, a hundred and twenty-eight points reach only 7.6·10⁻⁴ where the radius-two circle reached 1.4·10⁻¹³. Same problem, same routine, nine orders of difference, decided entirely by where the contour was drawn.

That gives the practical rule, and it is unusual in this field for being about input rather than about effort: move the contour before adding points. A circle placed in a gap converges so fast that the quadrature is free; a circle placed across a gap cannot be rescued by any amount of work that anybody would pay for.

What “digits per doubling” is measuring #

The third column is a ratio of logarithms and it is worth being careful about what it says, because a doubling is not the only way to spend.

Work here is the number of quadrature points N, and each point is one factorisation. The error behaves like ρ⁻ᴺ for a fixed ρ > 1, so log₁₀(error) is linear in N: each additional point buys a constant number of digits, and that constant is log₁₀ρ. Measured on the radius-two circle it is about 0.1 digits a point, which is the honest per-unit statement.

Doubling N therefore adds N·log₁₀ρ digits, and N is itself doubling — which is where the doubling third column comes from. So the sentence “each digit is cheaper than the last” is true of doublings and false of individual points, and both are worth having: the per-point rate is what a scheduler budgets, and the per-doubling rate is what a person deciding between 32 and 64 points experiences.

Compare an algebraic method, where the error goes like N⁻ᵖ. There log(error) is linear in log(N), so a doubling buys a constant p·log2 digits — 0.6 digits for the trapezoidal rule on a non-periodic interval, at every doubling, forever. That is the curve everybody has in mind, and it is what makes the table above surprising.

The halving has a range, and the range is short #

A table that stops at 128 points cannot say whether a trend continues. Carried three doublings further, on three contours:

Two things the four-point table could not show, and the second is the important one.

The ratio converges to two from above. 2.52, then 2.17, then 2.03 — so roughly doubles is a limit being approached rather than a description of the range measured, and the excess is the pre-asymptotic transient. It is also why the first entry of the gain column is 0.58 where the asymptotic law at N = 8 would give 1.6: the eight-point rule is not yet in the regime the rest of the table is in.

And it stops. The integral is a sum of a hundred and twenty-eight complex numbers computed in binary64, so its error cannot fall below the rounding level of that sum. At radius two it reaches 1.4·10⁻¹³ at 128 points, exactly zero at 256, and 4.4·10⁻¹⁶ from 512 onwards. Every doubling past about two hundred points buys no digits at all, so the price of a digit is not halving there — it is infinite. On this problem the essay’s headline holds for exactly four doublings and then the curve is flat.

That is not a footnote to the argument, it is the argument’s boundary. Improving with spending is the property that distinguishes this method from every other cost curve in the field, and it is bounded above by the arithmetic in a way the fixed, constant and worsening curves are not: a direct solve’s fixed price is fixed all the way to the rounding level, and a Krylov method’s constant rate runs until the residual floor. Here the improving rate runs out before the method has spent anything a large problem would notice — a hundred and twenty-eight factorisations is nothing, and it is already the whole of the useful range.

There is a reversal in it worth having. How many doublings the halving survives is set by the same g the rate is, and in the opposite direction: a contour with a small g starts further from the floor in point count, so it has more doublings of improvement available. Radius two, at g = 0.232, reaches the floor by 256 points; radius four, at g = 0.047, not until 1,024. So moving the contour into a gap improves the rate and shortens the range over which the rate keeps improving, which is the opposite of what the two properties sound like together. Both are still worth doing — a faster rate reaching a floor sooner is a better method — but the two sentences cannot be added.

The radius-four row also shows what happens outside the asymptotic regime, and it is not a slower version of the same curve. Its gains run 0.61, 0.92, 1.88, −0.34, 2.75, 6.06, 3.14: the error rises between 64 and 128 points, so the doubling law does not describe it at all until past 128 — which is exactly the range this essay’s table lives in, on a different contour. assertTheHalvingStopsAtTheRoundingFloor holds the convergence of the ratio from above, the arrival at the floor on all three contours, the zero gains past it, the reversal in the number of useful doublings, and the non-monotone stretch at radius four.

That row is worth drawing rather than only tabulating, because the exchange rate is not what a caller of this method actually wants. What they want is an integer.

Put side by side those two figures say the exchange rate is the wrong statistic. Radius 1.5 has the larger error and gets the answer right at every point count; radius 4 has an error four orders better than that at its finest and gets the answer wrong half the time. The quantity the method returns is a count, obtained by rounding, so what decides success is the distance from the sum to the nearest half-integer rather than the error’s size — and that distance is set by where the contour was put, not by how many points were spent on it. Doubling the points buys digits; it does not move an eigenvalue away from the contour, and no number of doublings will.

Where else this shape appears on the site #

Once named, the shape is recognisable, and it has appeared here twice before without being called out.

A multigrid V-cycle has a rate that does not notice the size, so its cost per digit is constant in the problem’s size — but constant per digit, not improving. A rate that does not notice the size is the strongest cost result in the iterative field and it is still a linear exchange.

Newton’s method genuinely doubles its digits per step, which is the same geometric shape at the level of an iteration rather than a quadrature. Its cost per digit halves at every step, exactly as here — and it is only available in a neighbourhood, which is the qualification a contour rule does not need.

And a Chebyshev interpolant of an analytic function converges geometrically for the same Euler–Maclaurin-adjacent reason. What all three share is analyticity: a smooth-but-not-analytic integrand has algebraic convergence, and the exponential rate is bought entirely by the integrand being extendable off the contour.

That is the sentence to carry into a cost argument: geometric convergence is a property of the data, not a property of the method. A contour rule applied to a non-analytic integrand is an ordinary trapezoidal rule with an ordinary O(h²) error, and nothing about it improves with spending.

The exchange rate is not the whole price #

Two costs sit outside the table and both matter.

Each quadrature point is a factorisation. The integrand needs T(z)⁻¹ applied to something, at a complex z, so every point costs one complex n × n factorisation — which here is a real 2n × 2n factorisation through the embedding, at eight times the price of an n × n one. A hundred and twenty-eight points is a hundred and twenty-eight factorisations, which for n in the thousands is the entire budget of the computation.

And the points are independent. Every one of them is a separate factorisation of a separate matrix with no data dependence on any other, which is the property a reduction that changes the order spends a whole essay wanting: a hundred and twenty-eight embarrassingly parallel factorisations, with one sum at the end. Compare a Krylov method, where step j cannot start until step j − 1 has finished, and whose cost model is dominated by that chain.

So the honest accounting is: expensive per digit in absolute terms, improving with spending, and perfectly parallel. Which is a combination no other method in this field has, and it is why contour methods are the ones used when the machine is wide rather than fast.

The other measurement in this field with an exact ratio #

The polynomial field supplies a second cost result, and it is exact rather than asymptotic.

A Krylov method for a quadratic eigenvalue problem can build its subspace out of the 2n × 2n linearisation or out of the coefficients directly. The second stores vectors of length n rather than 2n, and its projection is taken onto the quadratic, which has 2m eigenvalues for an m × m problem. So:

storage        exactly half
Ritz values    exactly twice
per number held    a factor of four

Measured at every subspace size from six to twenty-six vectors, on chains of sixteen to fifty-six masses, and exact at every one because both halves of it are counting rather than arithmetic. The essay that draws it is a Krylov space for a problem that is not linear, and what it adds to this one is the reminder that a cost ratio can be a theorem: no measurement was needed for the factor of four, only for the question of whether the cheaper basis is worth having, which is a different question and has a less comfortable answer.

Where the shift-and-invert saving is #

One more exact ratio, and it is the one that decides how a real problem is solved.

A shift-and-invert step for a quadratic needs Q(σ)⁻¹ applied to a vector. Q(σ) is n × n — it is λ²M + λC + K evaluated at a number — so the factorisation is of the original size, not of the linearisation’s. Factorising the 2n × 2n linearisation instead costs eight times as much and gains nothing: the shift is a number and the polynomial can be evaluated at it.

That is the same shape of saving as the same arithmetic at a different price — the work is identical and the arrangement is not — and it is the reason the practical methods in this field never form a linearisation at all. They evaluate the polynomial, factorise something of size n, and iterate.

The cost of the thing that is not the count #

A contour method is rarely run for the count alone, so the honest budget has to include the second integral — the moment ∮T(z)⁻¹V dz whose rank gives the eigenvalues.

It uses the same factorisations. At each quadrature point T(z) is factorised once, and then the count needs n solves for the trace while the moment needs ℓ solves for the probe block. So running both costs (n + ℓ) solves per point against ℓ for the moment alone, on top of one factorisation that is shared — which for n in the hundreds is a factor of about two, not a factor of two in the whole computation but in the cheap half of it.

Two integers for the price of one and a bit is the trade, and counting what is inside a circle is where the second integer earns it: the rank of the moment saturates at the smaller of the probe count, the number of eigenvalues inside and the size of the matrix, and only the independently computed count distinguishes those three.

Why the exchange rate matters more than the constant #

A final point of accounting, since it is the reason to care about the shape of a curve rather than about its height.

If a method’s exchange rate is constant, the decision about how much accuracy to ask for is a linear budget: twice the digits, twice the work, and a project can be planned against it. If the rate improves, the calculus inverts — the marginal digit is cheap, so the sensible policy is to overshoot rather than to tune, and the whole business of choosing a tolerance stops being worth the meeting.

Here the numbers say: whatever accuracy the eight-point run gave, the sixty-four-point run costs eight times as much and gives five more digits. Nobody should spend an afternoon deciding between them. Spend the eight times, and spend the afternoon on where to put the contour — where a factor of a hundred in ρ is decided, and where no amount of work substitutes for the choice.

What to carry #

Three sentences, and the first is the one that is unusual.

A geometric method’s exchange rate improves with spending, so the intuition that the last digit is the dearest is a fact about algebraic convergence rather than about accuracy. It survives everywhere else in this field because everything else here is algebraic or linear.

The rate is set by the input rather than by the effort. Where the contour is placed decides ρ, and ρ decides everything; adding points to a badly placed contour is the expensive way to discover that.

And the cheapest run is the one most likely to be wrong. The eight-point count on a circle of radius four returns minus two where the answer is four — a negative number of eigenvalues, from the cheapest row of the table. The exchange rate improving does not make the early rows safe; it makes them cheap, which is a different property, and the distance from the nearest integer is what tells them apart.

Where the shape breaks #

One boundary, and it is worth stating so that the finding is not over-generalised.

The doubling column doubles because the error is ρ⁻ᴺ with a fixed ρ. That holds while the quadrature is the only source of error. It stops holding at the rounding level: once the integral is computed to 10⁻¹³ the next doubling buys nothing at all, because what is left is the arithmetic rather than the truncation, and 256 points give the same answer as 128 for twice the price.

So the curve is geometric and then flat, and the useful policy is to stop at the knee. Measured here the knee is at about 128 points, where the error reaches 1.4·10⁻¹³ — which for an integer-valued answer is thirteen digits past what anybody needs.

The same shape appears in every geometric method on this site, and it is the reason four knobs and one floor exists: several parameters that each improve an answer share a floor, and past it the only thing more work buys is confidence that the floor is where it appears to be.