The eigenvalues that are answers to nothing

A rational approximant with five poles turns a 6 × 6 nonlinear eigenvalue problem into a 36 × 36 standard one. Thirty-six numbers come back. Six of them are the answer.

That ratio is not an artefact of a small example. The linearisation has n(m+1) rows by construction, so the fraction of returned values that mean anything is 1/(m+1) and falls as the approximation improves. A better approximation returns proportionally more noise. That is the opposite of the arrangement rank is a decision describes, where a better computation makes a decision easier; here it makes the sorting problem larger while making the answers better.

What the extras are #

They are not errors. Every one of the thirty-six is an exact eigenvalue of the matrix that was factorised, to the rounding level, and the factorisation did nothing wrong. They are eigenvalues of the approximant, and the approximant is a different function from the one that was asked about.

Of the thirty-six, twelve are real. Six lie in the target set and agree with the closed form to 6·10⁻⁴. The other six lie between −0.53 and −0.84, and the branch point is at −0.4.

Every one of them is past the branch point — to the left of it, where γ√(λ + c) is the square root of a negative number and is not a real quantity at all. The remaining twenty-four are complex and are discarded the same way.

The filter #

So the residual that is useless as a measure of accuracy is decisive as a filter, and it is worth being precise about the two roles.

Against the approximant, all thirty-six eigenvalues have a residual at rounding. That is the definition of an eigenvalue and it distinguishes nothing.

Against the original problem T(λ) = A − λI + γ√(λ + c)I, the six wanted values have residuals of 5·10⁻⁶ to 3·10⁻⁵ — small, and tracking the forward error as the problem the solver was actually given measures. The six spurious ones do not have a residual. Evaluating T there requires the square root of a negative number, so the quantity does not exist rather than being large.

That is a stronger separation than a threshold. A filter based on “reject anything whose residual exceeds ε” needs an ε and gets it wrong near the boundary; a filter based on “reject anything outside the domain of the function” needs nothing and cannot be marginal. The implementation reports Infinity with a flag rather than a NaN, because a NaN reaching a figure is a defect and a number outside a domain is a finding.

Why the extras sit there #

It is worth working out, because the location is what makes the filter work and it is not obvious that it should be that clean.

The approximated problem is det(A + c₀I − λI + Σ αⱼ/(λ − ξⱼ) I) = 0. Multiplying through by ∏(λ − ξⱼ)ⁿ turns it into a polynomial equation of degree n(m+1), which is where the count comes from. Its roots are the eigenvalues of the linearisation.

The rational function r(λ) matches γ√(λ + c) closely on the target set, so wherever the original equation has a root, so does the approximated one — those are the six. Away from the target set r is under no obligation, and in particular on the branch cut, where g does not exist, r is a perfectly ordinary rational function with poles on the cut and it oscillates between them. Between two consecutive poles it passes through every real value, including whatever value makes the approximated equation vanish.

So the extras are trapped between the poles, and the poles are on the cut by construction — because that is where they were put in order to approximate the singularity. The thing that makes the approximation good is the thing that puts the spurious eigenvalues somewhere identifiable — the same kind of accident the circulant that cannot be indefinite records, where a structure imposed for one reason forbids an outcome for a different one.

That is a piece of luck and it is worth saying so rather than presenting it as design. An approximant whose poles were somewhere else — in the complex plane, or scattered — would produce spurious eigenvalues scattered with them, and the filter would have to be a threshold after all.

Three kinds of eigenvalue that are not there #

This field now has three, and they are different in a way worth distinguishing because the word is the same in each case.

Eigenvalues of a linearisation at infinity, from an eigenvalue with no value: a singular leading coefficient sends some of the polynomial’s eigenvalues to infinity, and they are genuine features of the problem rather than artefacts. The count is a degree, computable exactly, and nothing about them is spurious — they simply are not finite.

Eigenvalues that are not eigenvalues at all, from the eigenvalues that are not there: a non-normal matrix whose computed spectrum moves enormously under a rounding-level perturbation, so the numbers returned are not close to any eigenvalue of the matrix that was handed over. A failure of the arithmetic, on the real problem.

Eigenvalues of the approximant, here: numbers that are exactly right about a problem nobody asked. Not a failure of anything. The arithmetic is correct, the object is correct, and the object is not the one in question.

The three need to be told apart because the responses differ completely. The first is counted. The second is a reason to distrust the computation. The third is filtered, cheaply, by asking the original function a question — and the filter works precisely because nothing went wrong.

What it costs to be careless #

A caller who takes all twelve real values as eigenvalues has six extra numbers between −0.53 and −0.84, in a region a physical problem might well care about. They are reproducible across seeds and precisions, so they do not look like rounding. And they have small residuals against the matrix any diagnostic would naturally check.

Everything about them looks like an answer except the one test nobody runs.

What refinement does to them #

Everything above is measured at m = 5, and the natural expectation is that adding poles adds extras — the count n(m+1) grows and the six answers do not. Sweeping m on the same problem:

Between eight and twelve poles there are no extras at all. Not fewer — none. Every real eigenvalue of a fifty-four-row or seventy-eight-row linearisation is one of the six answers, and the sorting problem this essay is about does not exist at precisely the pole counts where the approximation is best.

They return at fourteen and multiply, and the variable that governs it is not the pole count. κ of the linearisation grows like 10^(1.5m) and reaches 1/u at about m = 14, after which ‖g − r‖ stops falling as well: 8.7·10⁻⁸ at twelve, then 1.6, 1.8 and 1.5·10⁻⁸. Past that point the extra numbers are the eigensolver’s noise rather than eigenvalues of the approximant — they scatter as far as −24 instead of sitting between poles that reach only to −1 — and the count of wanted values goes 6, 6, 6, 6, 6, 6, then 8 and 12.

That last row is the one that matters, because it is the filter failing. Two spurious values at m = 16 and six at m = 20 land inside the target set, where the function is real, where a residual against T exists and is not large, and where the test that “cannot be marginal” has nothing to say about them. The filter is exact about the mechanism it was designed for and silent about the one that arrives when the linearisation stops being solvable.

So the account above describes m = 5 correctly and generalises the wrong way. There is a best pole count — eight to twelve here — at which the approximation is at its best and nothing spurious comes back, and what decides where that is is the conditioning of the linearisation rather than the quality of the fit. A caller choosing m by watching ‖g − r‖ fall would stop at fourteen or later, which is the first pole count at which the answer is contaminated.

Which suggests a diagnostic the essay did not have, and it is cheaper than the one it recommends. κ of the linearisation is the quantity to watch, and it is available before any eigenvalue is computed: it rises smoothly and predictably with m, it crosses 1/u at a pole count that depends on the problem, and every pathology above is downstream of that crossing. Watching ‖g − r‖ instead watches a quantity that goes flat because the crossing happened, which is a symptom reported one step too late — the same relationship a small residual is not a small error records between a residual and an error, here between an approximation error and a conditioning.

The rule that follows is short: add poles while κ of the linearisation stays under about √(1/u), and stop there. On this problem that is m ≈ 12, which is also where the approximation is best and where the filter has nothing to do. Three quantities that could have disagreed about the right answer, agreeing — which is a better position than the essay started in and is not one it could have reached from a single pole count.

That is the shape this site keeps recording and it is worth the repetition: the failures worth writing about are the ones where every available check passes. It is an eigenvalue count that cannot be slightly wrong turned inside out — there an integer is right or grossly wrong and cannot be subtly wrong; here a list of numbers is subtly wrong in a way that looks like being right.

And how much filtering there is to do depends on the approximant’s order, in the direction that makes the cheap approximant the dangerous one.

The wanted count never changes and the spurious count collapses to nothing. At 2, 3, 4 and 6 poles the linearisation carries 18, 24, 30 and 42 eigenvalues, of which 6 are wanted at every one — the problem’s own answer, unaffected by the approximation — while the number lying past the branch cut runs 12, 6, 0 and 0.

So the extras do not go away as the approximant improves — they move. The total grows steadily, 6 more eigenvalues per pole, and past four poles none of them sits in the region where the filter identifies them most easily. That is worth reading carefully, because it inverts the obvious economy: a two-pole approximant is cheap to build and hands the filter twelve candidates that announce themselves by being somewhere the function is not real, while a six-pole approximant is dearer and hands it thirty-six candidates none of which is disqualified by position. The cheap approximant produces more spurious eigenvalues and easier ones, and the filter’s work is not the count but the fraction that has to be tested against the original function rather than rejected on sight.

Counting rather than filtering #

There is a second route to the same question and it is worth naming because it comes from a different part of this field.

A contour integral counts the eigenvalues of T inside a region — the real T, not an approximant — and the count is an integral that is an integer. It needs no approximation, no linearisation and no filter; it needs the ability to solve with T(z) at points on a contour, which is available whenever T can be evaluated. A problem with infinitely many eigenvalues is that construction, and a ceiling with a knob on it is what it took to make it return the eigenvalues themselves rather than only how many there are.

So the two halves of this field answer the same question by opposite routes. Approximate-then-solve returns everything and requires a filter; count-then-extract returns only what is inside a region and requires a region. Neither is strictly better, and the useful observation is that the filter and the contour are the same test: both ask the original function about a candidate, and both work because the original function is available even though it cannot be linearised.

What a general implementation has to do instead #

The filter above works because this problem’s difficulty is a branch cut on the real axis and the approximant’s poles are on it. A general implementation cannot rely on that, and it is worth setting out what it does rely on, because the weaker version is still usable.

The weakest usable test is the residual against T, with a threshold. For a candidate λ and its vector x, compute ‖T(λ)x‖ / (‖A‖ + |λ| + |g(λ)|), which is a backward error for the original problem, and reject anything above a multiple of the approximation error ‖g − r‖. That threshold is available: it is the term the fit already measured, and a genuine eigenvalue’s residual is of that size by the tracking measured in the problem the solver was actually given, while a spurious one’s is of the size of the function itself.

The gap between those two is orders here — 3·10⁻⁵ against numbers of order one — so the threshold is not delicate, and the measurement that makes it safe is one this field already produces for a different reason. That is worth noticing: the quantity that says how accurate the answer is and the quantity that says which returned numbers are answers turn out to be the same quantity, used twice.

What the general test costs is one evaluation of g and one matrix–vector product per candidate, against n(m+1) candidates. On the example here that is thirty-six evaluations of a square root, which is nothing against the factorisation that produced them.

The two failure modes of the threshold version are worth stating. A candidate very close to a pole of the approximant can have a small residual against T by accident, because T(λ) is being evaluated where r is enormous and the comparison is dominated by scale — which is why the denominator carries |g(λ)| rather than being a fixed norm. And a genuine eigenvalue that the approximation moved a long way can be rejected, which is the same failure in the other direction and is a symptom that the target set was wrong rather than that the filter was.

The one thing to report #

An implementation that returns n(m+1) numbers has told its caller almost nothing. What it should return is the numbers that survived the filter, the count that did not, and the residual against T for each survivor.

The count matters as much as the list. Six wanted values out of twelve real ones is an ordinary outcome; six out of twenty would say the approximant has poles somewhere unexpected, and six out of seven would say the target set is admitting spurious values into its own window — which is what happens on a target set that reaches too close to the cut, — which is what a rank decision has to do when the gap closes, as the cheap rank and what it cannot see records — and is why the sweeps in an error committed before the arithmetic stop where they do.

None of those three numbers costs anything beyond what has already been computed. All three are thrown away by an interface that returns a list of eigenvalues.

The count of extras, as a diagnostic in its own right #

The number of returned values that survive the filter is worth watching across a sweep rather than at one setting, because how it changes says something the individual counts do not.

At two poles, eighteen eigenvalues come back and six survive. At five poles, thirty-six come back and six survive. At eight, fifty-four come back and six survive. The survivor count is constant while the total grows linearly, which is exactly the behaviour a correct construction should have: the problem has six eigenvalues in the region and the approximation degree does not change that.

A survivor count that grows with the degree is a signal, and it means one of two things. Either the target set is admitting spurious values into its own window — which happens when the region reaches close enough to the branch point that the poles and the region overlap, and is the reason the sweeps in a neighbouring essay stop where they do. Or the filter’s threshold is too loose and is passing near-poles, which the scaled denominator is there to prevent.

A survivor count that falls with the degree is the other signal and it is worse: it means genuine eigenvalues are being rejected, which happens when the approximation has moved one so far that its residual against T exceeds the threshold. That is the case where the target set is wrong rather than the filter, and adding poles is the fix rather than loosening the test.

So three numbers — the total, the survivors, and how the survivors move with the degree — give a diagnosis of which part of the chain is misconfigured, at no cost beyond a count. It is a small thing and it is the sort of small thing that turns an opaque failure into a legible one, which is what every measurement in this collection is ultimately for.

Why this does not happen in the rest of the field #

Worth one closing note, because a reader who has come through the polynomial field in order will not have met this before and might reasonably wonder what changed.

A linearisation of a matrix polynomial returns dn eigenvalues for a degree-d polynomial of size n, and every one of them is an eigenvalue of the polynomial. That is what the word linearisation means: the pencil’s elementary divisors match the polynomial’s, so nothing extra appears and nothing is lost. The quadratic field’s 2n numbers are all answers.

Here the object being linearised is not the problem. It is an approximation to it, chosen by the caller, and the extras belong to the approximation rather than to the construction. So the count n(m+1) is honest — that is genuinely how many eigenvalues T̃ has — and the mismatch is between T̃ and T rather than between the linearisation and T̃.

That is the same distinction the whole field turns on, arriving in the form of a list of numbers rather than of an error term, and it is perhaps the most concrete way to see it: a reader who has been told that the approximation is a separate error source can now count it.