The circle between two eigenvalues

The last digit is the cheapest counted the eigenvalues of a four-by-four delay problem inside a circle — the trapezoidal rule applied to $\frac{1}{2\pi i}\oint \operatorname{tr}(T(z)^{-1}T'(z))\,dz$ — and found a cost curve unlike any other in the field: the error falls geometrically in the number of points, so each doubling buys about twice the digits of the doubling before. It put the rate down to how far the integrand can be continued off the contour, measured “in the right conformal sense”, and it left the practical conclusion as a habit: move the contour before adding points.

Counting what is inside a circle said the same thing more plainly. The rate depends on the distance from the contour to the nearest singularity, not on how many singularities are inside, and a circle at radius 1.5, near the eigenvalue at 1.587, needs several times the points of one at radius two.

Both statements are right in spirit and both leave the one number a caller needs unstated: how many points, on which circle. That number turns out to be computable before a single point is spent, and computing it corrects both of them — the rate is not a distance, and the best circle is not the one furthest from the eigenvalues on either side.

The error is one term per eigenvalue #

The integrand $f(z) = \operatorname{tr}(T(z)^{-1}T'(z))$ is the logarithmic derivative of $\det T(z)$, so near each eigenvalue $\lambda$ it behaves like $1/(z - \lambda)$ and between eigenvalues it is analytic. On a circle of radius $R$ about the origin, the N-point midpoint rule — nodes at angles $2\pi(k + \tfrac12)/N$ — integrates each of those poles exactly in closed form, because a geometric series summed over the N-th roots of $-1$ has a closed form.

The result is short enough to state completely. An eigenvalue inside the circle contributes one to the true count and $1/(1 + q)$ to the computed one, with $q = (\lambda/R)^N$; so its error is $-q/(1 + q)$. An eigenvalue outside contributes nothing to the true count and $q/(1 + q)$ to the computed one, with $q = (R/\lambda)^N$. The count’s error is the sum of those terms over the whole spectrum — every eigenvalue, inside and out, each weighted by the $N$-th power of its modulus ratio to the circle.

That is a prediction with no free parameter, and the delay problem is a fair test of it because its spectrum is known in closed form through the Lambert W function: four real eigenvalues at 0.822, 1.587, 2.686 and 3.644, then conjugate pairs at moduli 4.191, 4.248, 4.388 and 4.560, then a second band of pairs from 10.76, and so on out through branches without end. Summing the terms out to the thirtieth branch and comparing with the quadrature computed from the matrix function itself, on 66 radii from 1 to 7.5 and 64 point counts from 8 to 512, gives 1,720 pairs where the error is large enough to compare — above $10^{-8}$ — and the worst disagreement is $5.7\times 10^{-7}$ of the error. Below $10^{-8}$ the comparison is with the quadrature’s own rounding, which on the larger circles is inflated by $e^{R}$-sized values of the integrand.

So the quadrature’s error is not governed by the nearest eigenvalue in the loose sense of an asymptotic bound. It is a sum of known terms, and the nearest eigenvalue’s term is merely the largest. Everything else in this essay is a consequence of reading that sum.

The rate is a ratio, not a distance #

Each term decays like the $N$-th power of a modulus ratio: $(\lambda/R)^N$ inside, $(R/\lambda)^N$ outside. The slowest of them is set by the two eigenvalues the circle falls between — $r_{\text{in}}$, the largest modulus inside, and $r_{\text{out}}$, the smallest outside — so the error falls like $\rho^{-N}$ with

$$\rho = \min\left(\frac{r_{\text{out}}}{R},\ \frac{R}{r_{\text{in}}}\right),$$

and each point buys $\log_{10}\rho$ digits. That is the dashed tent in the first figure: zero at every eigenvalue modulus, rising linearly in $\log R$ away from each, peaking where the two ratios are equal.

On the eighteen radii whose nearest eigenvalue is real and which sit off a gap’s balance point, the measured rate — the fall in $\log_{10}$ error per point over the last 32 points before $10^{-11}$ — agrees with this to 0.28 per cent at worst. Radius two, the circle both earlier essays used, has $\rho = 2/1.587 = 1.260$ and buys 0.1006 digits a point; the natural logarithm of that ratio is 0.232, which is exactly the “g = 0.232” the first essay reported without saying where it came from.

The word that has to change is distance. Two circles each 0.2 from their nearest eigenvalue — radius 1.022 beside the eigenvalue at 0.822, radius 2.886 beside 2.686 — converge at 0.0948 and 0.0312 digits a point, a factor of three apart, because $1.022/0.822 = 1.243$ and $2.886/2.686 = 1.074$. The same gap in absolute terms is a wide gap near the origin and a narrow one far from it. The quadrature on a circle sees the logarithm of the modulus, not the modulus, and the “right conformal sense” in which the first essay measured distance is exactly that: $\log R$ against $\log|\lambda|$.

This has a consequence nobody would guess from “distance to the nearest singularity”. A circle of radius seven, in the gap between the first band of pairs at 4.56 and the second at 10.76, sits 2.4 from its nearest eigenvalue and converges at 0.186 digits a point — faster than any circle in the gap between 0.822 and 1.587, where the largest possible distance is 0.38 but the ratio is only 1.93.

The price is the gap’s, and the count inside is irrelevant #

If a point buys $\log_{10}\rho$ digits and the best circle in a gap sets $\rho$ to the square root of the gap’s ratio, then ten digits cost about $20/\log_{10}(r_{\text{out}}/r_{\text{in}})$ points, whatever the circle holds. Measured at the midpoint of all eight gaps from the first eigenvalue to the second band of pairs, the product of the points for ten digits and $\log_{10}$ of the gap’s ratio lies between 20.6 and 26.5, while the points themselves run from 71 to 3,476 — a factor of forty-nine.

The labels in that figure are the refutation of the intuition that more eigenvalues cost more quadrature. The circle holding twelve eigenvalues is the cheapest of the eight at its midpoint, at 71 points. The circles holding six, eight and ten — inside the cluster of four conjugate pairs whose moduli sit within 9 per cent of each other — are the three dearest, at 3,476, 1,480 and 1,259. What makes the cluster expensive is not that it is crowded but that the gaps inside it are narrow in ratio: 4.248/4.191 is 1.0137, and $\log_{10}$ of that is 0.0059.

The open dots are the price a caller who wants only the integer pays, which is the price that matters for a count. The rounded answer is right from 4, 4, 9 and 24 points on the gaps between the real eigenvalues, 262, 99 and 109 inside the cluster, and 8 on the wide gap to the second band. Those sit between one and three points divided by $\log_{10}$ of the ratio, and near 1.5 on the narrow gaps: the integer costs between a ninth and a twenty-fifth of ten digits, which is the arithmetic of rounding — the error has to fall below a half rather than below $10^{-10}$. That is still a price in factorisations, one per point. An eigenvalue count that cannot be slightly wrong pays one factorisation in all, by Sylvester’s law of inertia, and the difference is what a symmetric linear problem gives that a delay problem does not.

So the cost of a contour count can be written down before it is run, given the moduli of the two eigenvalues the circle falls between. The difficulty is that a caller rarely has those — they are part of what is being computed — and that is where the essay’s last section ends up.

The best circle is not halfway #

Given two eigenvalue moduli, the obvious circle is the one halfway between them, where the contour is as far as it can be from both. The tent says otherwise: the two ratios $r_{\text{out}}/R$ and $R/r_{\text{in}}$ are equal at the geometric mean $\sqrt{r_{\text{in}}\,r_{\text{out}}}$, and that is where $\rho$ is largest. For the gap from 0.822 to 1.587 the midpoint is 1.204 and the geometric mean 1.142; for the gap from 4.56 to 10.76 they are 7.66 and 7.01. On the narrow gaps inside the cluster the two are indistinguishable and so are their prices.

That much is the balance argument, and it predicts a modest improvement: 70 points instead of 84 for ten digits on the first gap. What the measurement shows is different in kind. At the geometric mean of the first gap ten digits cost 27 points. On the next two gaps, 41 against 101 at the midpoint and 78 against 164. Not a modest improvement but a factor of two to three, and the large dots in the first figure sit at 0.37, 0.24 and 0.13 digits a point where the tent peaks at 0.14, 0.11 and 0.07.

The term-by-term formula says why, and it says it without approximation. An eigenvalue at $a$ inside contributes $-q/(1 + q)$ with $q = (a/R)^N$; one at $b$ outside contributes $+q'/(1 + q')$ with $q' = (R/b)^N$. When $a$ and $b$ are both positive reals and $R = \sqrt{ab}$, the two ratios are equal, so $q = q'$ and the two terms are equal and opposite at every N. They do not balance; they cancel, identically. What is left is the next pair out on either side — for the first gap, the eigenvalue at 2.686, with a ratio of 2.35 to the circle — and the count converges at that pair’s rate. The next-pair rate predicts 27, 41 and 79 points on the three gaps; the measurement gives 27, 41 and 78.

The notch in that figure is what the cancellation looks like at a fixed point count. Everywhere across the gap the measured error follows the one-term law, the two lines indistinguishable until the last few hundredths of the radius; at the geometric mean the measured error drops from the law’s $2.7\times 10^{-5}$ to $1.3\times 10^{-12}$.

Why it takes one ray #

The cancellation needs the two eigenvalues to point the same way. For an eigenvalue at angle $\theta$, $q$ carries a phase $e^{iN\theta}$, and a conjugate pair contributes twice the real part, $2|q|\cos N\theta$ in leading order. Two terms of equal modulus with phases $N\theta$ and $N\phi$ cancel at every $N$ only if $\theta = \phi$. At any other pair of angles they cancel at some point counts, add at others, and on average do neither.

Drawn by modulus and angle the delay problem’s spectrum explains the whole pattern at once. The four real eigenvalues lie on the ray at $0°$, so the three gaps between them cancel at their geometric means. The pairs lie between $103°$ and $117°$, each at its own angle — 4.560 at $109.8°$, 10.760 at $103.4°$ — so the wide gap between them has a balance point and no cancellation, and ten digits cost 57 points there against the one-term law’s 54.

Two details in that figure are worth reading. The measured curve lies above the dashed one by a factor of about six at the geometric mean, because a conjugate pair is two eigenvalues and the one-term law counts one, and the next pair out at 4.388 is only 4 per cent further in ratio. And the minimum, at 6.90 rather than 7.01, is where the particular phases at 24 points happen to line up best; at 48 points it moves. A gap between two rays has a best circle for each $N$ and none for all of them.

The cluster, where no single term dominates #

The dial on the second figure reaches radius four, which sits between the real eigenvalue at 3.644 and the first pair at 4.191, and its error does something the other circles do not: between 64 and 128 points it rises, from $2.2\times 10^{-3}$ to $4.8\times 10^{-3}$, before falling to $8.5\times 10^{-6}$ at 256. The first essay found the same stretch and called it pre-asymptotic.

The term-by-term sum calls it something more specific. Just outside radius four are eight eigenvalues within 9 per cent of each other in modulus and spread over seven degrees in angle, and at a few hundred points their terms are comparable in size, with phases that wander at different speeds. The error is a sum of eight rotating vectors of slowly separating lengths, and its modulus beats. The envelope still falls at the nearest pair’s rate, 0.0202 digits a point, but any window of 32 points can show a slope anywhere from negative to several times that — which is exactly what the small dots near $R = 4$ to $4.7$ in the first figure do.

That is the regime in which a stopping rule reading two successive errors is least reliable, because the error’s slope is not its rate. It is also the same eight eigenvalues on which where a contour budget should go found the whole tail of its unlucky probe blocks, with the four real eigenvalues safe in every draw. The count and the recovery are different computations with different failures, and both fail on the cluster.

What this does to the advice #

The advice both earlier essays ended on — move the contour before adding points — survives, and becomes a formula.

Price a circle before running it. Points for ten digits are about $20/\log_{10}(r_{\text{out}}/r_{\text{in}})$; points for a trustworthy integer a ninth to a twenty-fifth of that. A caller who knows roughly where the spectrum is can compare circles in advance and choose the one whose bounding ratio is widest, not the one furthest from the nearest eigenvalue.

Put it at the geometric mean. Always at least as good as the midpoint and, when the two bounding eigenvalues share a ray, a factor of two to three better, because their errors cancel outright. That is the ordinary situation for a symmetric problem, whose eigenvalues all lie on the real axis, and for any problem whose spectrum has a dominant direction.

Read the error when the moduli are unknown. Because the error is the sum of terms each fixed by one eigenvalue, the measured slope on a circle is $\log_{10}$ of a modulus ratio. A run that shows 0.10 digits a point at radius two has told its caller that an eigenvalue sits at $2/1.26 = 1.59$ or $2 \times 1.26 = 2.52$ in modulus — the first, in this problem — before any eigenvalue has been computed. The cost curve is itself a measurement of the spectrum.

What this does not change is the part of the price that is not points. The rate the condition number predicts and a rate that does not notice the size are rates per step with a fixed cost per step; here each point is one complex factorisation, the same size as the problem, and the formula above prices the number of factorisations and nothing else. And the floor four knobs and one floor describes is where every curve in the second figure flattens: about $10^{-15}$ for a circle whose integrand stays of order one, and higher on the larger circles, where $T(z)$ has entries of size $e^{R}$.

The spectrum being drawn here is a problem with infinitely many eigenvalues, and that turns out to matter less than it sounds. Every eigenvalue contributes a term, and the terms fall off as the modulus ratio to the $N$-th power, so beyond the next band out they are invisible at any point count anyone would use. An infinite spectrum costs exactly what its two nearest members say.

Still open: reading the moduli off the curve, and circles that are not centred at the origin #

The spectrum from the cost curve. A slope measured on one circle fixes the nearest modulus up to a choice of side; slopes on two circles fix it. The prediction is that from three runs of 64 points on radii 1.5, 2 and 2.5, the moduli 1.587 and 2.686 can be read to three figures without solving for a single eigenvalue — and that inside the cluster, where the slope beats, the same reading fails, which would make it a detector of clustering as well.

A centre off the origin. Everything here is measured on circles about zero, so “modulus” means distance from the origin. The terms are the same about any centre $c$ with $|\lambda - c|$ in place of $|\lambda|$, so moving the centre changes which eigenvalues share a ray. The prediction with a sign: centring a circle on the real axis between two real eigenvalues puts every real eigenvalue on one of two rays, at $0°$ and $180°$, and the ones on the far ray cancel with a sign flip — so there should be a best centre as well as a best radius, and it should buy another factor of two on a symmetric spectrum.

An ellipse around a stretch of the real line. For a spectrum that is an interval rather than a disc, the natural contour is an ellipse, and the conformal map that turns a circle’s logarithm of the modulus into an ellipse’s is the Joukowski map. The same one-term formula should hold in the mapped coordinate, and the geometric-mean rule should become a rule about the ellipse’s aspect ratio.