The conditioning that rises with the ceiling

A ceiling with a knob on it multiplies a contour eigensolver’s ceiling by the number of moments used, for no extra solves. The claim is true and it is not the whole price.

The moments are integrals of zᵖ against a fixed function, so their sizes grow like |z|ᵖ on the contour. A circle of radius four has ‖A₃‖/‖A₀‖ of order 64 before anything about the problem is taken into account. The block Hankel of K moments is therefore graded over ρ²ᴷ, its condition number rises at exactly the rate the ceiling does, and the rank decision it asks for gets harder at the rate the answer gets better.

The measurement #

Condition number of the block Hankel over the directions that carry an eigenvalue, for the delay problem with two probes:

Two knobs, and they multiply. The gap is ρ²ᴷ, so it is set by the radius as much as by the number of moments — a contour of radius fifteen and five moments is four orders apart from its own scaled version, where a radius of three is barely apart at all.

The division #

The repair is a change of variable. Integrate in

w = (z − c) / ρ

rather than in z, where c is the contour’s centre and ρ its radius. On a circle w is on the unit circle, so |w|ᵖ = 1 and every moment is the same size. The eigenvalues come back with c + ρ× applied at the end.

It costs one complex division per quadrature point — or, since the parameterisation is known, one multiplication by a unit vector already computed for the quadrature weight. In this implementation it is the difference between w = z and w = {re: cos θ, im: sin θ}, which is a line.

That the fix is a scaling should be no surprise by now. It is the units the matrix is measured in arriving in a place where the “units” are a coordinate on a contour, and it has the same character everywhere it appears: exact in both directions, approximating nothing, and deciding how many digits of the answer survive. That is the property a condition number scaling cannot move is careful to distinguish from the cases where a rescaling changes nothing — here it changes everything, because the grading is a coordinate rather than a fact about the problem.

Why it matters more than a factor of twenty sounds #

The number the conditioning spoils is not an eigenvalue. It is a rank, and a rank is a decision about a gap.

Rank is a decision is the essay about that, and the point transfers exactly. A block Hankel whose singular values are graded over ρ²ᴷ has directions that are genuinely present but scaled far below the largest — and a numerical rank test cuts relative to the largest. So the eigenvalues those directions carry are not merely computed inaccurately; they are not counted, and the method reports a smaller rank than the truth.

Which is the same failure the moments were introduced to fix. The ceiling was lifted from K·ℓ and replaced by a conditioning limit, and the second limit is worse than the first in one specific way: the first is a known integer that a caller can reason about, and the second is a number that depends on the contour and moves silently.

And the contour radius is the parameter that moves it, by six orders across the usable range.

Both climb and the gap between them does not close. At radii of 3, 5, 6, 10 and 15 the unscaled matrix reaches 3,071, 2.26·10⁶, 2.26·10⁶ and 7.37·10⁸ while the scaled one reaches 12.2, 695, 3.37·10⁴ and 3,952 — so the unscaled conditioning spans five and a half orders across the range and the scaled one two and a half.

The ratio is not monotone, which is the part that makes the parameter hard to choose. It runs 252, 3,250, 67 and 1.9·10⁵ at radii 3, 5, 10 and 15 — worst at the largest contour, best at radius ten, and with a factor of three thousand between neighbouring stops. A caller who measured the benefit of scaling at one radius and carried the number to another would be wrong by up to three orders in either direction. What is reliable is only the direction: the scaled version is better at every radius measured, by between 67 and 190,000 times, and the amount is not something the contour lets anyone predict.

The scaled version has neither limit until much later, which is what makes the division worth a section rather than a footnote. It is the same reading an eigenvalue count that cannot be slightly wrong gives to an integer computed from an inertia: a quantity that is an integer either arrives right or arrives obviously wrong, and one that arrives quietly small is the worse failure.

What the two versions agree about #

Both return the same rank while the conditioning allows it, and that agreement is what makes the comparison a measurement rather than a preference. At radius six and K = 3 both return six, and at K = 4 both return eight — the unscaled matrix is twenty and fifty times worse conditioned and still resolves the answer, because twenty and fifty are small numbers against 1/u.

The routes part where the argument says they should: when ρ²ᴷ approaches the reciprocal of the unit roundoff. At radius fifteen and five moments the unscaled gap is 1.9·10⁴, and pushing K further on that contour is where the unscaled version stops returning the right integer while the scaled one continues.

That is the same discipline every comparison of two algebraically identical routes on this site follows, from two Gram–Schmidts onwards: the interesting statement is not that one is better but where they stop agreeing, and whether the place was predicted before it was measured.

The Vandermonde underneath #

It is worth saying where the grading comes from, because it is the same object that makes the moments work at all.

The pth moment picks out the same sum over eigenvalues inside the contour that A₀ does, with each term weighted by λⱼᵖ. So the matrix relating the stacked moments to the eigenvector directions is a Vandermonde in the λⱼ, and it has full rank whenever the eigenvalues are distinct — which is precisely why K moments lift the ceiling.

A Vandermonde in points spread over a circle of radius ρ has entries growing like ρᵖ, and is notoriously ill conditioned when its points span a wide range of magnitudes. So the object that supplies the extra rank is the object that spoils the conditioning, and there is no version of the construction in which one appears without the other.

What the change of variable does is make the Vandermonde’s points lie on the unit circle instead, where they all have modulus one and the matrix is as well conditioned as a Vandermonde on distinct points can be. It does not remove the Vandermonde; it puts its points somewhere they can be told apart.

That is worth carrying past this essay, because it is the general shape of the repair whenever a graded object appears: the grading is usually a coordinate rather than a fact, and finding the coordinate in which it disappears is cheaper than working harder in the coordinate that has it.

The measurement that had to be constructed #

Getting the comparison to say anything took one repair worth recording, because the first version reported the graded matrix as the better conditioned of the two.

The obvious quantity is κ = σ₁/σᵣ, where r is the rank the routine decided on. Run that on both versions and at a small radius the unscaled one comes back three times better — which is not a measurement, it is an artefact: the two routines made different rank decisions, so σᵣ is the rth singular value of two matrices with two different r, and the comparison is between two different quantities.

The repair is to fix r from outside both routines. Here that is available, because the number of eigenvalues inside the contour is known from the closed form, so κ is taken over exactly the directions that carry one. Then the two numbers are about the same object and the comparison means what it looks like.

The general form of that mistake is worth naming, since it is easy to make in any comparison of two routines that each decide something. A quantity indexed by a routine’s own decision is not comparable across routines. A residual over the iterations a method chose to take, an error at the rank a routine selected, a cost at the tolerance an adaptive scheme settled on — each of them looks like a number and is a number plus a decision, and comparing two of them compares the decisions as much as the numbers.

What is left binding #

Three things, after the division.

The number of quadrature points, which decides the accuracy of every moment equally and is governed by the distance from the contour to the nearest eigenvalue outside it. Nothing here touches that.

The problem’s own size, since the ceiling is K·min(n, ℓ) and the n side of the minimum is not a choice. A contour holding more than K·n eigenvalues is under-resolved whatever the conditioning.

The eigenvalues’ own spread inside the contour. The Vandermonde is well conditioned when its points are spread on the unit circle and poorly conditioned when they cluster, so a contour containing a tight cluster of eigenvalues is harder than one containing the same number spread out, at every K, in both versions. That is a property of the problem rather than of the coordinate, and it is the one limit no change of variable removes.

The last of those is worth noticing because it is the same statement about the same object as the gap decides the eigenvector in the spectral field: what makes a cluster hard is that the directions being separated are nearly the same direction, and no amount of arithmetic recovers a distinction the data does not contain.

What a caller should set #

Two numbers, and the advice differs from the unlifted case’s because the conditioning changes the ordering.

Keep the probe block small — two or three. A probe is a whole extra set of solves round the contour and a moment is a multiplication, so the arithmetic argues for spending on moments. What the conditioning adds is that a probe costs nothing in grading: the block Hankel of K moments and ℓ probes is graded over ρ²ᴷ regardless of ℓ. So probes buy ceiling at a high arithmetic price and no conditioning price, and moments buy it at no arithmetic price and a conditioning price.

Raise K until the rank stops rising, and no further. The rank diagnostic is still the right one, and the conditioning gives it a second reading: a rank that falls as K rises is the signature of grading rather than of a smaller true count, and on a scaled construction it should not happen at any K a caller would reach.

Scale the contour variable, always. It is a line, it costs a multiplication already being performed, and it removes the second failure entirely up to the point where the Vandermonde’s own clustering binds.

The ordering between the first two is what changes with the radius. On a small contour the moments are free in both currencies and there is no reason to spend on probes at all. On a large one the grading is what limits K, and past that limit the only remaining knob is the probe block — which is expensive, and is the point at which splitting the contour into several smaller ones becomes the better answer.

Splitting the contour, which is the other answer #

The last paragraph named it and it deserves a section, because it is what a production implementation actually does and it changes which of the constraints binds.

A region containing forty eigenvalues can be handled as one contour with enough moments, or as four contours with ten each. The second costs four times the solves — the expensive resource — and every one of the four is a small contour with a small radius, so the grading is mild, the required K is small, and the Vandermonde’s points are spread over a region containing few eigenvalues rather than many.

The trade is therefore solves against conditioning, and it has the shape every trade in this collection has: the cheap resource runs out first. On a problem where each solve is a sparse factorisation, four contours is four times the dominant cost and is usually not worth it; on one where each solve is an iteration that converges quickly, it is nearly free and removes every conditioning question at once.

What makes the decision tractable is that both sides are measurable in advance. The number of solves is points × probes × contours and is known before anything runs. The grading is ρ²ᴷ and is known from the radius. So a caller can price both without computing an eigenvalue, which is the same arrangement the bound that is known in advance describes for a reduced model and which is rarer than it should be.

There is one genuine complication and it is worth flagging. Splitting a region requires knowing roughly where the eigenvalues are in order to split it sensibly, and an even split of a region whose eigenvalues are all in one corner produces one hard contour and three empty ones — which the empty-contour test at least reports rather than answering wrongly.

The two knobs, separated #

The sentence this essay exists for: a construction whose accuracy knob and whose conditioning are the same quantity has one knob, and finding the coordinate in which they separate is worth more than any amount of care in turning it.

Here the knob is K, the ceiling is K·ℓ, the grading is ρ²ᴷ, and one line of change of variable makes the second far less sensitive to the first. How much less is worth a number, because “independent” and “less sensitive” lead to different advice.

Condition number of the moment matrix, with and without the change of variable:

The scaled conditioning rises too — by a factor of 1,370 across six moments at r = 6. What the change of variable does is halve the exponent: the unscaled column grows by 1.25 decades per moment and the scaled one by 0.63, a ratio of 1.99. At r = 5 and r = 8 the same comparison gives 2.29 and 1.63, so the factor is about two and varies with the radius.

That is still the whole difference this section claims. At six moments it is 1,750 against 2,260,000 — three orders of magnitude, and the difference between a K that reaches six and one that does not. But a caller who reads the conditioning does not rise and takes K to twelve will find it near 10⁷ rather than near 1,750, and the honest form of the advice is the one already given above: raise K until the rank stops rising, and no further. Two different arguments now reach it.

And the scaling makes the conditioning depend on the radius where it did not. The unscaled column is the same number at every radius — 1.28, 13.4, 238, 5,850, 59,500, 2.26·10⁶ — while the scaled one runs 695, 1,750, 8,870 at K = 6 for radii of 5, 6 and 8. The change of variable divides by the radius, so a large contour is scaled harder and its moment matrix graded more.

Which sharpens the case for splitting a region: small contours help the conditioning twice, by holding fewer eigenvalues and by being scaled by a smaller radius. The section above priced that trade as solves against conditioning; the second half of the conditioning saving was not in the price.

Where the argument came from #

One note on provenance, since this measurement was not the one the work set out to make.

The higher moments were added to lift a ceiling that an earlier essay in this field had measured and left in place. The conditioning question arrived afterwards, from noticing that the moments’ sizes differ by ρᵖ — which is visible in the numbers as soon as they are printed, and is invisible in the derivation, where zᵖ is one symbol among several.

That is the ordinary way these things are found on this site: a quantity is printed for a different reason and its scale is wrong. The habit that produces it is printing the intermediate objects rather than only the answer, and the habit that would have missed it is checking that the answer is right — which it was, at every setting where the argument was first run.

The measurement then had to be constructed carefully, for the reason two sections above, and the first version of it said the opposite of the truth. Both halves of that are worth recording: the finding came from looking at a number nobody needed, and it came out backwards the first time it was measured.