A centre that chooses which pair cancels

The circle between two eigenvalues took apart the cost of counting the eigenvalues of a four-by-four delay problem inside a circle by the midpoint rule on $\frac{1}{2\pi i}\oint \operatorname{tr}(T(z)^{-1}T'(z))\,dz$. The count’s error is exactly one closed-form term per eigenvalue: $-q/(1+q)$ for an eigenvalue inside, with $q = (\lambda/R)^N$, and $+q/(1+q)$ for one outside, with $q = (R/\lambda)^N$. So each point buys a number of digits set by the slowest ratio, the best circle in a gap sits at the geometric mean of the two moduli it falls between — and when those two eigenvalues lie on the same ray, their terms are equal and opposite there at every $N$, and the count converges at the next pair’s rate instead.

Every circle in that essay was centred at the origin. It closed on the obvious second knob. “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.”

There is a best centre. The sign flip is a property of the point count, not of the ray. And the factor is two on one count, four on another and ten on the third, for a reason that has nothing to do with the far ray.

The law about any centre #

The first thing to settle is whether the term law survives the move. The derivation does not care where the centre is: the midpoint rule on a circle of radius $R$ about $c$ sees each eigenvalue through $(\lambda - c)/R$, and the same geometric series gives the same closed form. The delay problem — the one a problem with infinitely many eigenvalues introduced — has a spectrum known through the Lambert W function: real eigenvalues at 0.822, 1.587, 2.686 and 3.644, then conjugate pairs at moduli 4.19 to 4.56, then a second band from 10.76 — so the sum can be formed term by term and set against the quadrature computed from the matrix function itself.

On 143 circles and point counts, about eight centres from $-1$ to 3.6, the worst relative disagreement is $1.9\cdot10^{-8}$. Moving the centre changes nothing about the law and everything about which terms are large: an eigenvalue’s term falls like its ratio to the circle to the $N$-th power, and the ratio is measured from the centre.

The far ray flips only when N is odd #

With a real centre, every real eigenvalue lies on one of two rays — in front of the centre at $0°$, or behind it at $180°$. An eigenvalue behind the centre has $(\lambda - c)/R$ negative, so its $q$ carries a factor $(-1)^N$. That is the sign flip the prediction expected. It is a flip at odd $N$ and no flip at all at even $N$.

The cleanest way to see what that does is a circle built so that one eigenvalue on each ray has the same ratio. About $c = 1$, the eigenvalue 0.822 lies behind the centre at distance 0.178 and 1.587 in front at 0.587. At radius $\sqrt{0.178 \times 0.587} = 0.323$ the first is inside and the second outside, both at ratio 0.551.

At even counts the two terms are equal and opposite, exactly as two eigenvalues on one ray are at their geometric mean, and the count converges at the next eigenvalue’s rate: $1.9\cdot10^{-6}$ at 8 points, $3.4\cdot10^{-12}$ at 16, $4.5\cdot10^{-15}$ at 20 and $6\cdot10^{-18}$ at 24. At odd counts the term behind the centre changes sign, the two add instead of cancelling, and the error falls at the pair’s own rate: $9.4\cdot10^{-3}$ at 9 points, $7.4\cdot10^{-6}$ at 21, still above $10^{-8}$ at 29. The two curves come from the same circle and the same spectrum, and differ by eleven orders at 24 points.

So the prediction’s mechanism is half right, and the half that matters runs the other way. At the even counts every caller uses — and the counts here, like those in the earlier essays, are multiples of eight — an eigenvalue behind the centre behaves exactly like one in front of it. Two eigenvalues on opposite sides of the centre cancel across the circle just as two on one ray cancel across a gap. The far ray is not a different kind of ray; at even $N$ it is the same ray.

What a centre buys #

That makes the centre a second way to arrange a cancellation, and the question is what it is worth. For each run of the real eigenvalues a circle can hold alone, the cheapest circle about the origin — at the exact geometric mean, where the origin’s own cancellation lives — and the cheapest about any real centre, each in points for ten digits.

The figure at the top of the page is the table. About the origin, a circle can only hold runs that start at the first eigenvalue, and the first two, three and four cost 41, 78 and 341 points. About the best real centre the same three cost 22, 21 and 32: gains of 1.9, 3.7 and 10.7. Runs that do not start at the first eigenvalue have no origin circle at all, and cost between 20 and 38 points about their own best centres.

Single eigenvalues are left out of the comparison on purpose. The cheapest circle holding one eigenvalue alone shrinks onto it — radius 0.013 about 0.8219, six points — and its cost falls without limit as the radius does. That is a statement about already knowing where the eigenvalue is, which is the thing a count exists to find out.

The picture for four explains the factor of ten at a glance. A circle about the origin that holds 3.644 must have radius above 3.644 and below the first complex pair’s modulus, 4.19, and the best it can do is the geometric mean, 3.908. Its ratio to 3.644 is 0.933, and the complex pairs at angles near $110°$ sit at 0.86 to 0.93 of the way out. The real eigenvalue and the pair lie on different rays, so nothing cancels: five terms decay at 0.93 a point and ten digits cost 341. A circle about 2.3 of radius 2.85 holds the same four real eigenvalues and is a long way from the pairs — their distance from 2.3 is 5.6 to 5.8 — so every term sits between 0.47 and 0.52, and ten digits cost 32.

Drag to two and three and the circles shrink, and the origin’s circle stops being the obvious loser: it ends between two real eigenvalues, on one ray, and cancels them. The centre still wins, by less.

The centre does not add a cancellation; it chooses one #

How the best centres win is visible in the ratios themselves.

For the first two, the best centre is 1.10 with radius 0.879. Inside are 0.822, behind the centre at ratio 0.316, and 1.587, in front at 0.554; outside, 2.686 in front at 0.554 as well. The slowest pair — 1.587 inside, 2.686 outside — lies on one ray at one ratio and cancels, exactly as it would about the origin. What the centre changed is everything else: 0.822 has been pulled close, to 0.316, and the complex pairs have been pushed out to 0.18. The count converges at about 0.32 a point instead of the origin circle’s next rate.

For the first three it is the same arrangement one step along. About 1.43 with radius 1.673, 2.686 inside and 3.644 outside cancel at 0.754; 0.822 sits behind the centre at 0.36 and the pairs at 0.33. Twenty-one points, against 78 for the origin, which cancels the same pair but leaves 0.822 at ratio 0.26 — fine — and the pairs at 0.75, which is what costs it.

So the best centres in this spectrum use no cancellation across the centre at all. Every one of them cancels a pair on the near ray, as the origin does, and the advantage is that a centre can be put next to the eigenvalues that are not in the pair and far from the ones that are not real. A radius alone has one degree of freedom, and it is spent on the cancellation. A centre adds the second, and spends it on the rest of the spectrum. That is also why the gain is largest for four: there the origin has no cancellation to spend its radius on, and everything is left to the second knob.

The cheapest radius at every centre #

The best centre is not a knife-edge.

For each centre the radius is searched on a grid and at every geometric mean of an inside and an outside distance, because a cancellation sits at a single radius and a grid steps over it. For the first four the cost falls steadily from 341 at the origin to 32 near 2.3 and rises only slowly beyond — every centre from 1.7 to 3.55 costs under 50 points. For the first two and three the curves have a sharp floor. The cost falls as the centre moves right, pulling the eigenvalue behind it closer and pushing the complex pairs away; then it turns up steeply — 22 points at 1.1 for the first two, 44 at 1.3, 84 at 1.5, 410 at 1.7 — because moving further right carries the centre away from the eigenvalue it leaves behind and toward the neighbour that must stay out. The curve ends where those two are the same distance from the centre, 1.75 for the first two and 2.23 for the first three, past which no circle holds the run without its neighbour. The best centre sits well short of that wall.

The shape gives a rule a caller can use without the full spectrum. Put the centre inside the cluster to be counted, nearer the end with the neighbour that must stay out, and as far from the complex part of the spectrum as the cluster allows. Of the sweep’s centres for the first four that lie between the second and fourth real eigenvalues, every one costs less than a fifth of the origin’s circle.

Where the prediction stands #

The prediction had three parts. There is a best centre as well as a best radius: true, and the sweep shows it is a broad minimum for one count and a sharp one beside a wall for the others. The far ray cancels with a sign flip: the flip exists and is parity — at the even counts in use it is absent, and an eigenvalue behind the centre cancels with one in front exactly as two on one ray do. The best centres found do not need it; they cancel along one ray as the origin does. It buys another factor of two: 1.9 on the first two, 3.7 on the first three, 10.7 on all four. The factor grows with how badly the origin’s circle is placed, and it is worst placed where it has to pass between a real eigenvalue and a complex one.

That last point is the earlier essay’s own finding seen from the side. There, the circle at the geometric mean of two real moduli was cheap because the two terms cancelled, and the gaps that ended at a complex pair had a balance point and no cancellation. The origin is the wrong centre exactly when the gap it has to sit in is mixed. Counting what is inside a circle said a circle near an eigenvalue needs several times the points of one further away; the last digit is the cheapest said to move the contour before adding points. Both are about the radius. The centre is the larger knob, and it is the one the habit of drawing circles about the origin leaves unturned.

And the integer #

Ten digits is the earlier essays’ yardstick; a caller counting eigenvalues wants the integer, and the integer is right once the error stays below a half. About the origin the first two, three and four real eigenvalues need 4, 9 and 24 points for that — the same numbers the earlier essay found on those gaps. About the best centres they need 2, 3 and 5. The ratio is smaller than for ten digits, 2 to 5 rather than 2 to 10, because a half is reached early on any reasonable circle, but five factorisations against twenty-four is still the difference between a count that is nearly free and one that is not.

It is also the comparison an eigenvalue count that cannot be slightly wrong sets the floor for. A symmetric linear problem counts eigenvalues below a shift with one factorisation, by Sylvester’s law of inertia, and is exactly right or exactly wrong. A delay problem has no inertia to read, and the contour is the only count there is; five factorisations about a well-placed centre is as close to the symmetric case’s one as this problem gets.

Why this belongs to the cost field #

The quadrature here costs one factorisation of $T(z)$ per point, so points are factorisations, and a factor of ten is ten times the work. Where a contour’s budget should go divided a fixed budget between probes and moments and found four ways of reaching one ceiling four orders apart in accuracy, and a ceiling with a knob on it showed that a contour method returns at most as many eigenvalues as its probes allow. The centre is a factor of ten in the same currency, available before the budget is divided — and before the moments that raise the conditioning with the ceiling are spent — and it costs nothing to choose once the spectrum’s rough shape is known.

That condition is the honest limit. Every comparison here is between circles chosen with the spectrum in hand, as the earlier essay’s best radii were. A caller counting eigenvalues usually does not have the spectrum; the count is how they learn its shape. What carries over without it is the sweep’s shape, and the mechanism: about the origin, a cluster of real eigenvalues with complex neighbours of comparable modulus is the expensive case, and a centre placed inside the cluster removes the expense.

What one delay problem does not show #

The spectrum is one problem’s: four real eigenvalues on a line, and complex pairs at angles near $110°$ whose moduli are a little larger than the largest real one. A spectrum with complex eigenvalues close to the real cluster would leave a centred circle less room, and one whose real eigenvalues are spread over several decades would make the origin a better centre than it is here. Centres are restricted to the real axis; a centre off the axis would break the symmetry that pairs each complex eigenvalue with its conjugate, and nothing here measures what that costs or buys. And the point counts are for ten digits on the count’s real part; the integer a caller wants costs less, by the factor the earlier essay measured for the rounded count.

Still open: centres off the axis, the spectrum from two centres, and an ellipse #

A centre off the real axis. About a complex centre a conjugate pair is no longer symmetric, and each of its two members has its own ratio and its own phase. The prediction with a sign is that for counting a single complex pair with its conjugate, the best circle is about a real centre — moving the centre off the axis brings one member closer and pushes the other away, and the slower of the two always gets slower — so that the cost about any complex centre is at least the cost about the best real one.

Reading the spectrum from two centres. The earlier essay proposed reading eigenvalue moduli off the measured rate on two circles. With two centres the same reading gives two distances from known points, which fixes an eigenvalue’s position up to a reflection in the axis. The prediction is that rates measured over 64 points on circles about 0 and about 2 locate the real eigenvalue nearest each circle to three figures, and that the conjugate pairs come out with the right modulus and an angle accurate to a few degrees.

An ellipse around the cluster. A circle about 2.3 holding the four real eigenvalues wastes most of its area above and below the real axis. An ellipse with the same real extent and a smaller height keeps further from the complex pairs. The prediction is that the Joukowski map, which turns the midpoint rule on a circle into one on an ellipse, carries the term law over with each ratio replaced by its mapped value, and that the best ellipse costs at most two thirds of the best circle’s 32 points.