Where a contour's budget should go

A ceiling with a knob on it turned a hard limit into a product. A probe block of ℓ columns returns at most ℓ eigenvalues; stack K moments of the same contour integral into a block Hankel and the limit becomes K·min(n, ℓ), for no extra solves at all. A wall became a number the caller chooses.

A product invites a question that essay could only half answer. Twelve eigenvalues inside a circle can be reached by one probe with twelve moments, by two with six, by three with four, or by four with three. All four clear the same ceiling. They cost 512, 1,024, 1,536 and 2,048 complex solves, so the split that spends nothing on probes is a quarter of the price of the split that spends the most on them.

They are not four ways of doing one thing. Measured on a delay problem whose spectrum is a closed form, against the Lambert-W values rather than against a better computation, the four splits return the same twelve eigenvalues to 4.14·10⁻¹¹, 4.22·10⁻¹³, 1.60·10⁻¹⁰ and 4.89·10⁻¹⁵. Four orders separate the best from the worst; the cheapest is not the worst; and the ordering is not monotone, because three probes is worse than one.

The four splits, drawn one at a time #

The comparison holds everything but the split fixed: the same problem of size four, the same circle of radius six, 512 quadrature points, the same random block generator, and enough moments computed in the single pass round the contour that no split has to walk it twice. The number inside is twelve, checked against the integral that counts what is in a region rather than assumed, and the rank of the block Hankel comes back as twelve at every one of the four settings. What moves is the accuracy, and nothing else.

The cheapest split is one probe and twelve moments. It walks the contour once with a single right-hand side, which is 512 complex solves, and every moment after the first is one multiplication at each quadrature point.

Eleven digits for a quarter of the solves is a good trade and it is the trade the earlier essay recommended. Doubling the block to two columns doubles the solve count and drops the moment count to six, which is the split that essay measured as the best of the three it looked at.

Two orders for twice the solves is a different kind of trade, and the natural reading is that it is the start of a trend. Three probes is the next rung, at 1,536 solves and four moments, and if accuracy rose with the width of the block it would land somewhere below 10⁻¹³.

It lands at 1.60·10⁻¹⁰, which is worse than one probe. Three probes costs three times the solves of one and returns an answer half an order less accurate, and there is nothing in the derivation that predicts it. The rank is twelve, the count is twelve, the stopping diagnostic is satisfied, and every published quantity says the run succeeded.

The ordering is the block Hankel’s conditioning, digit for digit #

The four splits build four different matrices out of the same integrals. One probe and twelve moments gives a block Hankel that is 48 × 12; two and six gives 24 × 12; three and four and four and three both give 12 × 12. Only the twelve columns are common, because the ceiling is the same.

Their condition numbers, measured over the twelve directions that carry an eigenvalue rather than over whatever each split’s own rank decision happened to keep, order the four splits in exactly the order the errors do:

Measuring κ over the twelve carried directions rather than over each split’s own kept rank is not a detail. Taking the largest singular value over the last one a split decided to keep compares four matrices with four different numbers of columns, and at a small radius that makes the most graded of them look like the best conditioned. Fixing the count at twelve — the number the region actually holds, which the trace integral supplies independently — asks one question of all four.

Both columns are medians over ten random probe blocks, for the reason the next section is about. The ratio of the two columns is 1.54·10⁻¹⁶, 6.94·10⁻¹⁷, 1.31·10⁻¹⁶ and 1.03·10⁻¹⁶ — four numbers inside a factor of 2.2 of each other, all of them the unit roundoff. The error is the conditioning times the arithmetic, at every split, across four orders of both.

That is a satisfying answer and it is only half an explanation, because it moves the question rather than closing it. Why the conditioning runs 66, 871, 518,000, 1,550,000 in that order is not something the derivation says. Half of it is the grading the conditioning that rises with the ceiling measures: the moments grow like the radius to the power of their index, so a block Hankel of many moments is graded whatever else is true, and ℓ = 4 with three moments is better conditioned than ℓ = 2 with six for that reason alone.

The other half is not explained by grading at all. One probe with twelve moments is the most graded of the four and it is better conditioned than three probes with four, which has a third as many moments. Every measurement here already integrates in the scaled variable, so the grading has already been divided out once, and what is left is a property of how the twelve eigenvalue directions distribute themselves over ℓ columns. That is a real gap in the account, and it is the reason the recommendation at the end of this essay is stated as a measurement rather than as a rule.

One draw is not a distribution #

Every number so far is one probe block. The block is a matrix of independent normal entries, and the method’s answer depends on it — which makes a single reported error the same kind of statistic that an answer that changes with the seed is about, and that the variation that comes with a seed argues should be reported as a band rather than as a line.

Ten blocks, at the same four splits, on the same contour:

The two rows worth reading against each other are the second and the fourth. In the median they are a factor of six apart. In the worst case they are four orders apart. Six is nothing — a caller choosing between two probes and four on the strength of a single run would be choosing on noise, and would reasonably take the one that costs half as many solves. Four orders is the whole finding.

The shape of the ℓ = 2 column is what makes it a tail rather than a spread. Seven of its ten draws land between 2.0·10⁻¹⁴ and 9.6·10⁻¹⁴, which is a tight and well-behaved distribution. The other three are 4.22·10⁻¹³, 2.85·10⁻¹² and 5.82·10⁻¹⁰, and the last of those is four orders past the median with nothing in between. The ℓ = 4 column has no such structure: its ten values run from 4.89·10⁻¹⁵ to 3.24·10⁻¹⁴ and the largest is 6.6 times the smallest.

The conditioning model breaks on exactly that one draw, which is worth recording because it held so well everywhere else. The unlucky block’s κ is 6.26·10², entirely ordinary against a median of 8.71·10², so the error is 9.31·10⁻¹³ times its conditioning — four thousand times the unit roundoff, where every other draw at every other split sits within a factor of ten of it. Whatever goes wrong on that block is not visible in the block Hankel’s condition number over the directions it keeps.

The tail sits on eight eigenvalues, not on twelve #

The twelve eigenvalues inside the circle are not alike. Four are real — 0.8217, 1.5866, 2.6862 and 3.6442 — and the other eight are four conjugate pairs with moduli 4.1908, 4.2483, 4.3883 and 4.5604, which is a cluster of eight values spread over four tenths of a unit near the edge of a contour of radius six.

Split the worst error over ten draws by which group it falls in and the tail has an address:

At two probes the four well-separated eigenvalues are safe in every draw — the worst of forty readings is 4.17·10⁻¹⁴ — and the entire four-order tail is on the cluster. That is the failure the earlier essay described in words and did not measure: a probe block has to have a component along every eigenvector inside the contour, it has one with probability one, and the size of that component decides how visible the corresponding direction is. Eight nearly coincident directions seen through two columns is where a draw gets to be unlucky, and it is the same quantity a sketch of a constrained problem turns on: a random block reaches every direction, and whether it reaches them well is a separate question with its own answer.

At four probes the clustered eight are the best-resolved group on the page.

Why the fourth split has no tail at all #

There is a reason ℓ = 4 behaves differently in kind rather than in degree, and it is not accuracy. The problem has size four. A block of four random columns spans the whole space with probability one, so there is no direction left for it to be short of, and the method stops being randomised.

That is measurable, and the measurement is unusually clean. Taking the values the method returns from one moment and comparing them across ten draws, the spread is 2.12 at one probe, 1.20 at two and 0.861 at three — the answer moves by more than a unit depending on the block. At four probes the spread across ten draws is zero to eleven decimal places, and it stays zero at six probes and at twelve.

The same thing happens at the working setting. The widest disagreement between any two of the ten draws about the same eigenvalue is 6.61·10⁻¹⁰ at one probe, 5.82·10⁻¹⁰ at two and 1.66·10⁻⁹ at three, and 3.29·10⁻¹⁴ at four. Below the size of the problem the method returns a different answer to every block and reports none of that; at the size of the problem it returns one answer.

So the four-order gap between two probes and four is not a gap between two accuracies. It is the gap between a sampled subspace and a basis, and the reason it shows up in the tail rather than in the median is that a sample is usually fine.

Where the ladder stops, and what widening past it buys #

The ceiling is K·min(n, ℓ), and the min is the part a caller reading “K times ℓ” will drop. Past ℓ = n a wider block buys nothing at all.

Three times the solves, the same rank, the same median to a factor of two — and a worst case that gets worse rather than better, because the extra columns are linearly dependent on the first four and the arithmetic that decides which directions to keep now has more numbers to lose digits in.

It is worth being exact about how far that generalises, because ℓ = n is reachable here only because n is four. On a problem of size four a probe block of four columns costs four sweeps round the contour and the ceiling min(n, ℓ) is met by walking to it. On a problem of size ten thousand it is not a setting anybody reaches, and the whole of this comparison lives in the regime where ℓ is far below n and every column is a sample rather than a basis. What survives the change of scale is the tail rather than the recommendation: the four-order gap at two probes is a property of eight clustered eigenvalues seen through too few columns, and a larger problem has more clusters and no more columns.

The strongest version of the point is what happens to a caller who takes the ceiling as K·ℓ literally. Twelve columns and one moment reads as a ceiling of twelve, which is exactly what is inside the circle, at 6,144 solves. The rank comes back as four. The method returns four values — 4.3986, 5.0994, 6.0319 and 6.8336, all real, all outside or on the edge of the contour they were supposed to be inside — and not one of them is within 0.75 of any eigenvalue in the region. They are eigenvalues that are answers to nothing, returned at three times the cost of the split that gets all twelve to fourteen digits.

And those four numbers are the same four numbers a block of four columns returns at one moment, agreeing to 1.00·10⁻¹², across all ten draws. Eight extra columns and 4,096 extra solves changed the answer in the twelfth digit. That is why the drawing routine refuses a probe block of twelve on a problem of size four rather than drawing it: the picture would be identical to the one at four columns and would carry three times the price in its caption.

Does the ordering survive a different contour #

Two changes are worth making, because a conclusion drawn at one radius on one problem is a conclusion about that radius.

Pulling the contour in to radius five keeps all twelve eigenvalues inside — the outermost has modulus 4.5604 — and improves every split, because the moments are less graded on a smaller circle. The separation narrows with it. Over ten draws the median at two probes is 2.18·10⁻¹⁴ against 1.06·10⁻¹⁴ at four, a factor of 2.1, and the worst case is 3.59·10⁻¹³ against 2.09·10⁻¹⁴, a factor of 17. The tail is still there and it is one order rather than four.

That is the honest shape of the recommendation. The gap between the two best splits is not a constant of the method; it is set by how hard the contour makes the problem, and it grows with the radius exactly as the grading does.

Shrinking the circle further changes the question rather than the answer. Radius four holds four eigenvalues, so the ceiling to clear is four rather than twelve, and one probe reaches it with four moments. It returns 4.61·10⁻¹⁰, which is worse than any twelve-eigenvalue reading at two or four probes. Fewer eigenvalues to find did not make the split a good one; the block is still one column against four directions, and one column is where the trouble was the whole time.

What ten draws can and cannot support #

The central claim of this essay is about a worst case, and it rests on ten random blocks at each split. That is a small sample and it should be said plainly what it can carry.

It supports the existence claim, which is the one that matters for a caller. A block that costs four orders at two probes was drawn on the first attempt, in a sample of ten, on a problem chosen for having a closed form rather than for being difficult. Existence needs one instance and there is one. It also supports the comparison in the direction it is made: forty readings at four probes produced nothing above 3.24·10⁻¹⁴, while ten at two probes produced one at 5.82·10⁻¹⁰.

It does not support a rate. Whether an unlucky block is one in ten, one in fifty or one in a thousand is not something ten draws can say, and this essay does not say it. Nor does it support a distribution: three of ten above the tight cluster is consistent with a heavy tail and with a bimodal draw and with several other shapes, and separating those needs the kind of sample a bound that holds with probability is written against.

What removes the need for the rate is the fourth split. If the tail’s frequency were the deciding question, it would have to be measured. It is not, because at ℓ = n there is no draw left to be unlucky in — the spread across draws is zero to eleven decimals, which is a statement about the algebra rather than about a sample.

What follows for a caller with a budget #

The ceiling is a product, so a budget is a choice about which factor to buy, and the four measurements above give it a shape.

Spend on probes up to the size of the problem, and on moments after that. Four probes on a problem of size four costs four times the solves of one probe and returns fourteen digits instead of eleven, with a spread across draws of 6.6 rather than four orders. That is the recommendation the earlier essay’s own explanation implied and its three-point table could not reach, because the point that settles it is the fourth.

Do not read a single run as the method’s accuracy. Two probes at radius six reports 4.22·10⁻¹³ on the draw the drawing routine happens to use, which is the seventh best of ten and neither the median nor the tail. A method whose answer depends on a random block should be run at two blocks before its error is quoted, and the second run costs what the first did.

A wider block than the problem is a receipt, not an improvement. Rank four at 6,144 solves is the same rank four at 2,048, and the caller who widened has bought a longer bill and, in the tail, a worse answer.

Check the rank against the count, not against the ceiling. The trace integral gives the number inside for one pass round the contour, and every split above returns rank twelve against a count of twelve — which is why the accuracy had to be measured against an answer that is known rather than inferred from the diagnostics. Every one of these runs looks converged.

That last point is where the ceiling and the tail turn out to be the same subject. The original defect was a method that returns two eigenvalues out of twelve and says nothing about the other ten. The moments fixed it, and what is left is smaller and has the same shape: a method that returns twelve eigenvalues to four digits fewer than usual, on a block it will not mention, with every diagnostic reading correctly. The repair is the same in kind — make the answer stop depending on the thing nobody is looking at — and here it costs solves rather than multiplications.