Count the upper half, read the lower

A centre that chooses which pair cancels moved a contour count’s circle along the real axis and found it worth a factor of 1.9 to 10.7 on the delay problem’s real eigenvalues: about the best centre the four of them cost 32 points for ten digits, against 341 about the origin. The centre did not add a cancellation between eigenvalue terms. It chose which pair cancelled and pushed everything else away. The essay kept its centres on the axis, and said so: “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.” Its prediction was that it costs. “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.”

That is measured here, and for one circle it is right without exception. It also turns out to be the wrong question about cost. A set closed under conjugation does not have to be counted on one circle, and a problem with real coefficients pays for only half of the circles it uses. Counted that way, the same sets cost less than half as much once they hold four bands or more.

The law off the axis #

Every number below rests on the closed form that the circle between two eigenvalues found for the midpoint rule on a circle. Each eigenvalue contributes one term to the count’s error: $-q/(1+q)$ if it is inside, with $q = ((\lambda - c)/R)^N$, and $+q/(1+q)$ if it is outside, with $q = (R/(\lambda - c))^N$. A term falls like its ratio to the circle to the $N$-th power, and the price of ten digits is set by the slowest ratio the circle cannot avoid. The earlier essay checked the law about real centres. The derivation does not care whether the centre is real, but the imaginary part of the error was zero by symmetry about a real centre and is not about a complex one, so both parts are checked here.

On 83 circles about six complex centres — in the first cluster, in the second, between the bands, beside the real eigenvalues — at radii from 0.4 to 4 and point counts from 8 to 64, wherever the quadrature’s error is above $10^{-8}$, the sum of terms matches the quadrature computed from the matrix function itself to a relative $4.1 \cdot 10^{-8}$ in both parts. The law moves with the centre. So the price of any circle can be read off the spectrum, and the questions below are questions about geometry.

The delay problem is the one a problem with infinitely many eigenvalues introduced: four real eigenvalues at 0.822, 1.587, 2.686 and 3.644, then bands of four complex eigenvalues each, with their conjugates. The first band sits near $-1.7 \pm 4i$, the next near $-2.5 \pm 10.6i$, and they continue about 6.3 apart in the imaginary part — $\pm 17.0i$, $\pm 23.3i$, $\pm 29.7i$, $\pm 36.0i$ — each a little further left and each tighter than the last. The sets counted are the four real eigenvalues with the first $m$ bands, $4 + 8m$ eigenvalues closed under conjugation, for $m$ from one to six.

One circle: the prediction holds #

For each of the first three sets and each distance of the centre from the axis — 0, 0.25, 0.5, 1, 1.5, 2 and 3 — the centre’s real part and the radius are searched for the cheapest circle that holds exactly that set.

Every step away from the axis costs more, on all three. With one band the price goes 52, 56, 59, 71, 93, 139 and 567; with two, 97, 98, 111, 142, 186, 273 and 1,766; with three, 150, 158, 171, 214, 278, 401 and 3,251. At an offset of a quarter the loss is a few per cent, and at an offset of three it is a factor of eleven to twenty-two. No circle about a complex centre beats the best about a real one, on any of the sets, which is what the prediction said.

The picture shows the mechanism. Lifting the centre brings it nearer the upper cluster and further from the lower, and the circle has to hold both. So its radius grows — 6.93 on the axis, 7.07 at an offset of one, 7.36 at two, 9.50 at three — and a bigger circle is a circle closer to the next band, the eigenvalues it must not hold. On the axis the slowest term is the second band’s, at a ratio of 0.658; three units up, its slowest ratio is 0.96, and ten digits need 567 points. The prediction’s reason was about the pair it holds, one member slower as the other speeds up. The measurement says the cost comes from what the circle must exclude. The direction is the same.

The real part moves too, and not monotonically: at offsets of 0, 1, 2 and 3 the best centres sit at 0, $-1.44$, $-1.06$ and then $+3.96$, where the circle swings right to keep the next band’s lower-left clusters out. That is a sign that the single circle has run out of good choices rather than found a new one.

Two ways to hold the same set #

One circle has to do two jobs at once. It has to reach every eigenvalue in the set, and it has to stop before every eigenvalue outside. On the delay problem those two requirements meet across the gap between the last band held and the next, and the gap is the problem: the bands are 6.3 apart, at a distance from the centre that grows with each band, so the ratio across the gap climbs towards one. Holding the real eigenvalues and one band, a circle about the origin of radius 6.93 has its slowest ratio at 0.658. Holding six bands, the best circle has radius 39.0 and its slowest ratio is 0.923.

Nothing requires the set to be held by one circle. Counts add: the number of eigenvalues inside two disjoint circles is the sum of the numbers inside each. So the same set can be counted as the four real eigenvalues on one circle about their best real centre and each band’s upper cluster on a small circle of its own. Every one of those circles sits in a gap that does not shrink. The real eigenvalues’ circle is the one the earlier essay found; it costs 32 points alone and needs the complex bands only to stay away. A cluster’s circle holds four eigenvalues lying within a third of a unit of its centre, in a gap of five to six on every side.

That leaves the lower clusters, and here the problem’s own structure pays. The delay problem has real coefficients, so its matrix at a conjugate point is the conjugate of its matrix, $T(\bar z) = \overline{T(z)}$, and the integrand of the count, $\operatorname{tr}\,T(z)^{-1}T'(z)$, does the same. Take the midpoint rule about $\bar c$ with the same radius and point count: its nodes are the conjugates of the nodes about $c$, its values the conjugates of the values there, and its sum the conjugate of the sum. The count about $\bar c$ is the count about $c$, read off without a single evaluation. Measured on all six clusters at their own point counts, the two agree to $1.6 \cdot 10^{-15}$. A count closed under conjugation needs its upper half counted and nothing more. It is the same trade a factorisation with nothing to pivot for describes for Cholesky, where the symmetry a general method ignores is half the work, made here in a quadrature instead of an elimination.

So the comparison has three prices: one circle about the best real centre; the split with every circle evaluated, mirrors included; and the split with the mirrors read from the upper circles for free. To compare like with like, the split is held to the same accuracy on the whole count as the one circle is. Its pieces — the real eigenvalues, $m$ upper clusters and $m$ mirrors, $1 + 2m$ in all — each get an equal share of the $10^{-10}$, so each is counted to $10^{-10}/(1+2m)$, which costs the real eigenvalues’ circle 37 to 39 points instead of 32.

What the split costs #

At one band the split loses. One circle costs 52 points; the split costs 37 for the real eigenvalues and 18 for the upper cluster, 55, and 73 if the mirror is evaluated. The real eigenvalues’ circle is the expensive piece, and a single band’s gain does not pay for it.

From two bands on the split wins, and the margin grows with every band. One circle costs 52, 97, 150, 192, 234 and 275 points for one to six bands; the split with the mirrors free costs 55, 68, 83, 92, 104 and 115. At six bands that is 0.42 of one circle’s price. Even paying for the mirrors — the split a code would use on a problem without real coefficients, where $T(\bar z)$ and $T(z)$ are unrelated — ties at two bands, 99 against 97, and wins from three: 127 against 150, and 191 against 275 at six.

The increments say why the gap keeps opening. Each band adds 41 to 53 points to one circle, about forty-five on average. Each band adds 9 to 15 to the split: one cluster’s circle at 10 to 14 points, and a point or two to the real eigenvalues’ circle as their share of the budget tightens. Both prices grow linearly in the number of bands, but at rates four times apart.

The plane shows what the two strategies are spending on. At three bands the single circle has radius 20 about $-2$; it has to pass between the third band at distance 17.1 from its centre and the fourth at 23.3, and almost all of its area is empty plane that holds no eigenvalue and contributes nothing to the count. The split’s circles have radii 0.68 to 1.26 around the clusters and 2.87 around the real eigenvalues, each fitted to what it holds. Drag to one band and the one circle shrinks to radius 6.93 about the origin, close enough to its set that the split has nothing to gain; drag to three and the empty plane inside the single circle is most of the picture.

A gap that shrinks and a gap that does not #

The two growth rates come from the slowest ratio each circle has to outrun, and that ratio is a property of the spectrum.

For one circle the ratio is 0.658, 0.799, 0.857, 0.889, 0.909 and 0.923. Those are close to the square roots of consecutive band distances’ ratios — a circle balanced at the geometric mean between distances $d_m$ and $d_{m+1}$ has both terms at $\sqrt{d_m/d_{m+1}}$ — and with the bands evenly spaced in the imaginary part, $d_m/d_{m+1}$ tends to $m/(m+1)$. Ten digits take about $10/\log_{10}(1/\rho)$ points at a ratio $\rho$, and with $\rho^2 \approx m/(m+1)$ that grows like $46m$. That is the forty-five a band.

For a cluster’s own circle the slowest ratio falls instead: 0.267 for the first band, 0.152 for the second, and 0.096 by the sixth, because each band’s four eigenvalues are tighter than the last, and the gap around them stays at about six. Ten digits at a ratio of 0.1 cost ten points, and that is the price of a band in the split. The real eigenvalues’ circle sits at 0.51 throughout. Its slowest terms are the real eigenvalue nearest its edge and the first band’s clusters, and the bands further out do not reach it.

That is the general shape. A single circle’s price is set by the gap between what it holds and what it must exclude, measured as a ratio of distances from its centre, and a set that extends outwards makes every such ratio worse. A split’s price is set by the gaps around each piece, and pieces can be chosen so that those do not change. Where a contour’s budget should go found the same kind of thing one level up, in how a contour method should share its solves between probes and moments: the cheapest arrangement is the one that spends where the information is, and a circle drawn around empty plane is spending where none is.

Where the prediction stands #

The prediction was that “the cost about any complex centre is at least the cost about the best real one”, and for a single circle holding a set closed under conjugation it holds at every offset and on every set measured: the price rises at each step off the axis, by more than four times at an offset of three. Its reasoning was about the wrong eigenvalues, the pair the circle holds rather than the band it must exclude, and its conclusion still comes out right.

What it did not consider is that a set closed under conjugation is two halves of one count, and that a problem with real coefficients hands over the second half for nothing. The best centre for one circle is on the axis because one circle has to hold both halves. The cheapest count is the one that stops trying to: the real eigenvalues on the axis, where the earlier essay found a centre for them, and each upper cluster on a circle of its own above it. The mirror symmetry the earlier essay was afraid of breaking is what pays for the split.

What the split assumes #

It assumes the clusters are known. Placing a circle around four eigenvalues a fifth of a unit apart is something a code can do only after it has found them, or at least found where they are to within the gap around them. Counting what is inside a circle introduced the count as the way to learn how many eigenvalues are in a region before looking for them, and a split built from the answer is a second count, not a first. That is the same caveat the earlier essay attached to single eigenvalues, whose cheapest circle shrinks onto the eigenvalue: a count is cheap in proportion to what is already known about the spectrum. On the delay problem the bands are known in closed form through the Lambert W function, and on a real problem they would come from a first, coarse count. A coarse count needs only the integer, which the earlier essay priced at two to five points about its best centres, and an integer is a different kind of answer from ten digits: an eigenvalue count that cannot be slightly wrong is the case for why, since it is either right or wrong by a whole eigenvalue. So the plan is a cheap coarse count, then a split at full accuracy where it matters.

It also assumes the problem is real. The free mirror is $T(\bar z) = \overline{T(z)}$ and nothing weaker: a complex coefficient anywhere breaks it, and the split then costs the mirrored price, which still wins from three bands here but only by 15 to 31 per cent. And it counts each circle’s real part to its share of ten digits; the imaginary part, which is zero on a real-centred circle by symmetry, is not zero on a complex one and is not used. A code that checked the imaginary part as a sanity test of the count would see the two halves’ imaginary parts cancel exactly, by the same conjugation.

What one delay problem does not show #

One problem, whose bands are evenly spaced and get tighter. On a spectrum whose clusters spread as they go out, the split’s pieces would grow and its advantage shrink; on one with no clusters at all — complex eigenvalues spread evenly along a curve — there is nothing to fit a small circle around, and the split degenerates into one circle per eigenvalue, which only makes sense once the eigenvalues are known. The midpoint rule on circles only. The last digit is the cheapest found that a contour count buys its digits at a constant price once the rate is set, so the comparison in points for ten digits carries over to other accuracies by proportion, but other contours — ellipses, rectangles — change the ratios themselves. And the search for each best circle is on a grid of centres a quarter and a tenth of a unit apart, refined by halving; the prices are those of circles found that way, and a finer search could shave a point or two off either side.

Still open: an ellipse around the cluster, and the integer #

An ellipse around the real eigenvalues. The split’s dearest piece is the real eigenvalues’ circle, 32 to 39 points, and it spends most of its area above and below the real axis, where there is nothing to hold. The earlier essay’s prediction for the four real eigenvalues alone was that the Joukowski map carries the term law over to an ellipse and that the best ellipse costs at most two thirds of the best circle’s 32 points. If it does, the split’s advantage grows on every row. The prediction with a sign is that, with the real eigenvalues on the best ellipse, the split costs less than 0.4 of one circle at every band count from three to six.

The integer. Ten digits are what a residue check wants; a count wants the integer, which is right as soon as the error is under a half. The earlier essay found the rounded count 2 to 5 points about the best real centre. The prediction is that the rounded count of the split is cheaper than one circle’s rounded count at every band count from one to six — including one band, where the split loses at ten digits — because the integer needs only the first half-digit, and a cluster’s circle, with its slowest ratio under 0.27, should reach it in very few points while one circle’s ratio of 0.66 to 0.92 cannot.