Two groups need two reductions

The scaling that buys ten orders repaired a quadratic eigenproblem written in bad units with two lines: Fan, Lin and Van Dooren’s γ and δ, computed from three norms, which turn λ²M + λC + K into a problem whose coefficients are of comparable size. Measured over eight decades of units it took the backward error from $10^{-4}$ back to $10^{-15}$. The essay then named a limit. The tropical roots — the corners of the max-plus polynomial $\max(\log\lVert M\rVert + 2x, \log\lVert C\rVert + x, \log\lVert K\rVert)$ — divide the eigenvalues into two groups when $\lVert C\rVert^2 > \lVert M\rVert\lVert K\rVert$, and one γ cannot put both groups near one. The device the literature offers is to scale twice, once at each tropical root, and keep from each run the group its root predicts. On the essay’s chain the two roots were a factor of a hundred apart and one scaling sufficed: “What would ask for one is a problem whose two groups are twenty decades apart.”

An estimate that does not move then found the tropical roots right about the large end of the spectrum and constant at the small end, and its section on the two corners noted that a second scaling “rather than a sharper estimate” would be the remedy where the corners are far apart. Neither essay built that problem. This one does, and the second scaling does not help. The thing that does is not a scaling.

That figure is where the two roots came from and what they were trusted for: the large one tracking the top of the spectrum to within a few per cent at every size, the small one constant while the bottom of the spectrum fell. At a damping of 6 the roots are a factor of twenty apart and everything in this essay is invisible. The question is what happens as the factor becomes ten orders, and then twenty.

A chain with its groups pulled apart #

The problem is the overdamped chain both essays used: eight unit masses joined by unit springs, $K$ the tridiagonal of 2 and −1, and damping $C = \alpha M + \beta K$ with β = 0.5. Its sixteen eigenvalues are real and known in closed form, two per mode of the chain. Raising α separates them. The large group sits near $-\alpha$; the small group, one eigenvalue per mode, near $-\kappa_j/\alpha$; and the separation $\lVert C\rVert^2/(\lVert M\rVert\lVert K\rVert)$ grows like $\alpha^2$. At $\alpha = 10^{0.78}$, the earlier essays’ value of 6, it is 21. At α = 10⁶ it is $4.2\cdot 10^{11}$, the tropical roots are $2.4\cdot 10^{-6}$ and $10^6$, and the two groups are twelve decades apart. At α = 10¹² the separation is $4\cdot 10^{23}$.

The solver is the site’s own: the first companion pencil of the quadratic, reduced to a standard eigenvalue problem by inverting one of its coefficients, then Francis’s algorithm. Every eigenvalue is scored twice — by its backward error, $\sigma_{\min}(Q(\lambda))/(|\lambda|^2\lVert M\rVert + |\lambda|\lVert C\rVert + \lVert K\rVert)$, which needs no eigenvector, and by its relative distance from the closed form. Five routes are compared: the leading reduction, $-A_1^{-1}A_0$, as given; the same after Fan–Lin–Van Dooren scaling; the same after tropical scaling at each root in turn, the small group taken from the run at the small root and the large from the run at the large one; the trailing reduction, $-A_0^{-1}A_1$, whose eigenvalues are the reciprocals $1/\lambda$; and both reductions, the large group from the leading and the small group from the trailing.

No scaling keeps the small group #

The figure at the top of the page is the worst backward error over the small group against the separation.

Unscaled, the leading reduction’s small group loses accuracy at almost exactly the rate the separation grows: $1.3\cdot 10^{-15}$ at a separation of 21, $9\cdot 10^{-13}$ at $4\cdot 10^5$, $1.3\cdot 10^{-8}$ at $4\cdot 10^9$, $2.7\cdot 10^{-7}$ at $4\cdot 10^{11}$, and by $4\cdot 10^{15}$ a backward error of 0.026 — no eigenvalue at all in any useful sense. At the extreme separation, $4\cdot 10^{23}$, the small eigenvalues it returns are wrong by up to a factor of $10^9$: not perturbed answers but invented ones, with every digit set by the rounding of the large group. The dotted line is the unit roundoff times the separation, and the measured line runs along it, a factor of ten or so beneath.

Fan–Lin–Van Dooren’s scaling does not move it: $7.1\cdot 10^{-7}$ at $4\cdot 10^{11}$, within a factor of three of unscaled at every separation. The tropical scalings do not move it either, and at the small root they are slightly worse: $10^{-5}$ at $4\cdot 10^{11}$. Across every separation past $10^6$, all three are within a factor of a hundred of each other. The prediction that a second scaling would rescue the small group, which both earlier essays made in passing and the literature makes in general, fails on this problem at every separation it was meant to cover.

The trailing reduction is flat. Its small group’s worst backward error is between $3.5\cdot 10^{-16}$ and $7.4\cdot 10^{-16}$ at every separation from 21 to $4\cdot 10^{23}$.

And no reduction keeps both #

The large group is the mirror image. The leading reduction keeps it at rounding — $2.9\cdot 10^{-16}$ to $8.6\cdot 10^{-16}$ up to a separation of $4\cdot 10^{11}$, and at most $2.2\cdot 10^{-12}$ beyond it — and so do both scalings of it. The trailing reduction loses it, along the same line the leading reduction lost the small group: $1.5\cdot 10^{-9}$ at $4\cdot 10^7$, $1.9\cdot 10^{-5}$ at $4\cdot 10^{11}$, and 0.3 at $4\cdot 10^{15}$.

Eigenvalue by eigenvalue the pattern is complete. At damping $10^6$ the leading reduction gets the eight large eigenvalues to $1.6\cdot 10^{-15}$ and the eight small ones to no better than $6.7\cdot 10^{-6}$; the trailing reduction gets the small ones to $6.6\cdot 10^{-15}$ and the large ones to $10^{-4}$. Turn the dial: at $10^2$ the two reductions disagree in the twelfth digit, at $10^4$ in the ninth, at $10^8$ in the first. Each is right about exactly one end. Take the large group from one and the small group from the other and every one of the sixteen eigenvalues is right to $10^{-13}$ up to a separation of $4\cdot 10^{15}$, and to $1.2\cdot 10^{-11}$ at worst beyond it.

Six routes to one spectrum compared the two reductions and three linearisations on a badly scaled problem and found them differing by a factor of forty. Here they differ by the separation itself, and the difference is not noise between them: it is two halves of one correct answer, split by which end each reduction can see.

Why scaling cannot do it here #

A Schur factorisation of an $N \times N$ matrix $A$ computes the eigenvalues of a matrix within about $u\lVert A\rVert$ of $A$, so an eigenvalue of modulus $|\lambda|$ is resolved to relative accuracy about $u\lVert A\rVert/|\lambda|$ — fine for the eigenvalues near $\lVert A\rVert$, hopeless for those many orders below it. The leading reduction’s matrix $-A_1^{-1}A_0$ has a norm of the order of the large group, $\lVert C\rVert/\lVert M\rVert$, and the small group sits a factor of the separation below that. The figure sets this prediction against the measurement: it gets the slope exactly — one decade of error for each decade of separation, on both reductions — and overstates the level by a factor of two to two hundred, which is the distance between a norm bound and the eigenvalues’ actual sensitivity.

Now scale. Fan–Lin–Van Dooren’s substitution λ = γμ and multiplication by δ change the pencil to $(\delta\gamma^2 M, \delta\gamma C, \delta K)$. δ cancels the moment one coefficient is inverted. γ changes the reduced matrix by a diagonal similarity and a factor of γ in every eigenvalue, so both $\lVert A\rVert$ and every $|\mu|$ are divided by roughly the same γ, and their ratio — the separation — is unchanged. A scaling that balances a pencil for a method that works on the pencil, as the QZ algorithm does, is not the same thing as a scaling for a method that inverts one coefficient first, and on a pencil reduced this way the ratio that decides the loss is a property of the eigenvalues, not of the units. The tropical scaling at the small root does change the balance — it makes $\delta\gamma^2\lVert M\rVert$ tiny and $\lVert A_1^{-1}A_0\rVert$ correspondingly larger — which is why it is a little worse rather than better.

The trailing reduction does what no scaling can: it inverts the other coefficient, so its matrix’s norm is of the order of the small group’s reciprocals, and the small eigenvalues, read as $1/\mu$, are now the large ones. That is the repair the scaling that buys ten orders pointed to for a spectrum that comes in reciprocal pairs, where a palindromic quadratic’s two groups are reciprocal by structure: “neither one scaling nor two, but a division”. The essay read that as one of three repairs for one symptom in three families; measured here, the overdamped chain needs the same repair as the palindromic family once its separation is large, and the division is what the second reduction is.

The reference had the same defect #

The first version of this measurement reported forward errors of infinity for the small group, from every route including the trailing reduction that was backward stable to $10^{-16}$. The fault was in the reference. The chain’s closed form computes each mode’s two roots as $(-b \pm \sqrt{b^2 - 4k})/2$, and for the small root that subtracts two numbers that agree to as many digits as $b^2$ exceeds $4k$ — the separation, again. The figure shows the formula’s own error growing along the same dotted line as the leading reduction’s: $4\cdot 10^{-12}$ at a separation of $4\cdot 10^3$, $7\cdot 10^{-5}$ at $4\cdot 10^{11}$, and from $10^{16}$ an exact zero. Every chain measured in the essays before had b under ten and lost nothing visible.

The repair is the textbook’s own second sentence: compute the large root from the formula, and the small one as $k/\lambda_{\text{large}}$ from the product of the roots. It is now in the closed form every quadratic essay here is checked against, with a note saying why. It is worth stating plainly what the episode shows, because it is the same lesson as the eigenvalues’: the closed form and the leading reduction both computed the small group by a route whose arithmetic was set by the large one, and both lost the separation in digits. An answer that is known is the standing argument for exact references, and it holds only if the exact answer is computed by a route that is itself exact for the part being measured.

What this changes about the tropical roots #

The tropical roots keep their best use, and it is not the one the second scaling assumed. As an estimate that does not move found, they locate the large end well and the small end poorly. What they are reliably good for is the separation itself: $\lVert C\rVert^2/(\lVert M\rVert\lVert K\rVert)$, computed from three norms before anything is solved, predicts the slope of the loss on whichever group the chosen reduction cannot see. A code that reads it can decide in advance whether one reduction is enough — at a separation of about $10^4$ the small group has already lost four digits of forward accuracy, and each further decade costs one more — or whether it must run both and keep each one’s own group, which costs a second factorisation and a second Schur decomposition and nothing else.

What a solver would do #

Put as a procedure, the measurement says this. Compute the three norms and the separation $\lVert C\rVert^2/(\lVert M\rVert\lVert K\rVert)$; it costs three passes over the coefficients. If it is small — a few hundred, as on every chain measured before — one reduction is enough and the choice between them does not matter. If it is large, reduce twice: once inverting the leading coefficient, keeping the eigenvalues whose moduli exceed the geometric mean of the two tropical roots, and once inverting the constant coefficient, keeping the rest. The boundary is where the tropical roots are actually reliable, because it is set by the two corners together rather than by the small one alone, and on every damping measured here it fell cleanly between the groups — eight eigenvalues on each side at every separation.

The cost is a second factorisation of one coefficient and a second Schur decomposition of a $2n \times 2n$ matrix: twice the work of one solve, against a loss of one digit per decade of separation without it. A code that wants only one group — the slow modes of a heavily damped structure, which are the small group — needs only the trailing reduction, and pays nothing extra at all; it simply has to know that the default is the wrong one. Eigenvectors follow the same rule, since each reduction’s Schur vectors are accurate for the eigenvalues it resolves and not for the others.

What the procedure does not need is a scaling. Fan–Lin–Van Dooren’s γ and δ remain the right repair for the problem they were measured on — coefficients in bad units — and the earlier essay’s ten orders stand; what they cannot do is turn one matrix into two, and a problem with two groups decades apart needs two.

The condition number that did not move #

The loss in this essay is not the eigenvalues’ own sensitivity. The number that moves when the problem does separated two quantities offered as an eigenvalue’s condition number: one, built from the coefficients’ norms and the eigenvalue together, unmoved by an exact change of variable; the other inflated by it. The trailing reduction’s flat backward error at every separation is the first quantity’s verdict made visible — the small eigenvalues of these chains are well conditioned with respect to perturbations of the coefficients, and a method that respects their scale computes them to rounding. The leading reduction’s loss is therefore the method’s, not the problem’s, in exactly the sense a backward-stable answer to a problem nobody asked meant: the reduced matrix’s eigenvalues are computed stably, and the problem whose eigenvalues they are is not the quadratic’s at the small end.

That distinction is what makes the two-reduction remedy cheap rather than heroic. Nothing about the small group needs higher precision, an iterative refinement or a structured algorithm. It needs to be computed by the arithmetic of its own scale, and a reduction that inverts the constant coefficient is that arithmetic, already written, behind a flag that defaults to the other end.

What eight masses do not show #

One family, real eigenvalues by construction, eight masses, one linearisation and a standard-eigenproblem route. A QZ algorithm applied to the pencil without inverting either coefficient is the setting in which the tropical scalings were designed and proved, and it is not measured here; the claim refuted is about tropical scaling under a reduction to one matrix, which is how this site’s solver, and many simple codes, compute the eigenvalues. Complex eigenvalues, a family with three groups, and larger chains are all untested.

Still open: the pencil itself, and a third group #

QZ on the scaled pencil. The tropical scalings were proposed for an algorithm that works on the pencil $A_0 + \lambda A_1$ without inverting either matrix. The prediction with a sign is that under QZ the tropical scaling at each root does rescue its own group, so that the two-scaling remedy and the two-reduction remedy give the same sixteen eigenvalues to rounding — and that the unscaled QZ loses the small group at a rate set by the coefficient norms rather than by the separation, which would put the cause of this essay’s loss precisely in the inversion.

A cubic with three groups. A cubic matrix polynomial can have three tropical roots and three groups. Two reductions see two ends; the middle group is the one neither inverts, and whether a scaling at the middle root rescues it under either reduction, or whether it needs a shift-and-invert at the middle root, is the case that would say how far the two-reduction remedy generalises.