An interior root needs its own scaling

The middle group needs no reduction of its own built cubic matrix polynomials whose twelve eigenvalues fell into three groups up to eight decades apart and asked which reduction of the companion pencil keeps which group. A matrix polynomial $P(\lambda) = \sum_k A_k\lambda^k$ is solved by linearising it into a pencil $\lambda X + Y$ of $d$ times the order and reducing that pencil to a standard eigenproblem, either by inverting $X$ — the leading reduction, which keeps the largest eigenvalues — or by inverting $Y$ — the trailing reduction, which keeps the smallest. Two groups need two reductions had found that a quadratic with two groups needs both. The cubic’s middle group was the worry: inverted by neither, it might need a third route. It did not. The leading reduction kept it at $10^{-11}$ or better at every separation, the trailing reduction lost it, and the reversed polynomial’s leading reduction — inverting the same constant coefficient as the trailing one — kept it, which located the trailing reduction’s loss in the pencil rather than in the end it inverts.

Its last section made two predictions. “A quartic has two interior groups. If what was measured here is a rule — interior groups are kept by both the leading reduction and the reversed polynomial’s — then two reductions still suffice for four groups. The prediction with a sign is that at eight decades between groups both interior groups are kept by the leading reduction to $10^{-11}$ or better, and that no group needs a third route; the alternative, which would say the middle of a cubic is special, is that the second-lowest group of a quartic is lost by the leading reduction as the small group is.” And: “The second companion pencil is the first’s transpose, with the coefficients down a block column instead of across a row. The prediction is that its trailing reduction keeps the middle group as the reversed route does, and that the middle-group loss is therefore a property of one linearisation’s layout rather than of reducing at the bottom.”

The alternative of the first prediction is what happens, and then more than it. The second prediction fails.

Four groups, a decades apart #

The quartics are built the way the cubics were. Each coefficient is $U\,\mathrm{diag}(c_k)\,V^{\mathsf T}$ for fixed random orthogonal $U$ and $V$, and each diagonal entry is a scalar quartic whose four roots sit near $10^{-3a/2}$, $10^{-a/2}$, $10^{a/2}$ and $10^{3a/2}$ — four groups, $a$ decades apart, sixteen eigenvalues in all for an order-four polynomial. That is the structured family, in which every coefficient shares one diagonal form; the generic family adds to each coefficient an independent random matrix of three tenths of its norm, which breaks the shared form and is what a real problem looks like. Five seeds each, separations of two, four, six and eight decades — the last a spread of twenty-four decades from the smallest eigenvalue to the largest.

Every computed eigenvalue is scored by its backward error, the smallest singular value of $P(\lambda)$ over $\sum|\lambda|^k\|A_k\|$: the size of the relative perturbation of the coefficients that would make it exact. The eigenvalues are grouped at the geometric midpoints of the tropical roots, the four numbers read off the coefficients’ norms that predict where each group sits, and each route is scored by its worst error in each group. Nine routes: the leading and trailing reductions of the first companion pencil, the reversed polynomial’s leading reduction, the leading and trailing reductions of the second companion pencil, and the first pencil’s two reductions after a tropical scaling at the second and at the third root.

The leading reduction loses the interior #

The figure at the top of the page shows the eight-decade case, and the first row is the first prediction’s answer. The leading reduction of the first companion pencil keeps the largest group at $6 \cdot 10^{-16}$ and returns the third group at $4 \cdot 10^{-2}$, the second at $3 \cdot 10^{-2}$ and the smallest at $10^{-1}$. Both interior groups are wrong in their second digit.

The separation sweep shows how it goes. At two decades the leading reduction keeps everything to $10^{-11}$ — the smallest group at $7 \cdot 10^{-12}$, the rest near rounding. At four the smallest group is lost and the interior groups are kept. At six the second group is lost — $3 \cdot 10^{-2}$ — while the third is kept at $5 \cdot 10^{-11}$. At eight the third goes too. The groups are lost from the bottom up, one per two decades of separation: the reduction keeps what is large compared with the coefficient it inverts, and as the groups spread, more of them fall below what that inversion can resolve.

So the alternative the essay offered — “the second-lowest group of a quartic is lost by the leading reduction as the small group is” — is what happens, at six decades and beyond. The cubic’s middle group was kept by the leading reduction because at eight decades it sat eight decades below the large group, and that is within what the inversion of the leading coefficient resolves. A quartic’s second group sits sixteen decades below its largest at the same separation. Whether a group survives the leading reduction is a question of its distance from the top, not of its being interior.

The structured family resists longer, as the cubic’s did. With every coefficient sharing a diagonal form the second group under the leading reduction stays between $5 \cdot 10^{-9}$ and $2 \cdot 10^{-8}$ from four decades on, never lost outright but never within the predicted $10^{-11}$, and the third group stays under $5 \cdot 10^{-11}$ throughout. Structure delays the loss; on the generic family, which is what the prediction would be applied to, it does not prevent it.

No unscaled route keeps the second group #

The first prediction had a second clause: “no group needs a third route”. Before the scaled routes come in, the five unscaled ones can be asked the question group by group — for each group, the best of the leading and trailing reductions of both companion pencils and the reversed polynomial’s leading reduction.

At two, four and six decades some unscaled route keeps every group — the worst over the four, taking each from its best route, is $4 \cdot 10^{-14}$, $10^{-12}$ and $7 \cdot 10^{-11}$, with the reversed route carrying the second group. At eight decades the best any unscaled route does on the second group is $3 \cdot 10^{-2}$. Every one of the five loses it. The trailing reductions keep only the smallest group, the leading reductions only the largest, and the reversed route, which kept the cubic’s middle group, keeps only the smallest. The second group of an eight-decade quartic sits eight decades above the smallest and sixteen below the largest, and no pencil that inverts an end coefficient resolves anything that far from its own end.

Two reductions, each scaled at an interior root #

The remedy that the scaling that buys ten orders opened the subject with is a tropical scaling: substitute $\lambda = \tau\mu$ for a tropical root $\tau$ and divide the coefficients by the largest of $\tau^k\|A_k\|$, so that the group near $\tau$ becomes a group near one and the coefficients around it are balanced. Applied at the second tropical root and followed by the trailing reduction, it keeps the smallest group at $4 \cdot 10^{-16}$ and the second at $10^{-13}$ at eight decades. Applied at the third root and followed by the leading reduction, it keeps the third group at $3 \cdot 10^{-14}$ and the largest at $6 \cdot 10^{-16}$. Each scaled reduction keeps the two groups on its own side of the middle, and the two together keep all four.

Across the sweep the pair’s worst over all four groups is $2 \cdot 10^{-14}$, $9 \cdot 10^{-13}$, $10^{-10}$ and $10^{-13}$ at two to eight decades, against the unscaled routes’ $3 \cdot 10^{-2}$ at eight. So the clause “no group needs a third route” is true in the letter and false in the spirit: two reductions suffice, but not the two the cubic used. Each must be scaled at the interior root beside the groups it is responsible for, and a quartic’s two halves are two cubic-like problems, each with its own middle.

The cubic was the case where that distinction did not show. With three groups, the leading reduction’s “end” is the large group, and the middle group is one step from it; scaling at the middle root was not needed because the unscaled leading reduction already reached one step. With four groups at the same separation, each end reduction still reaches one step and no further, and the second step needs its own scaling.

The second companion form loses what the first loses #

The second prediction placed the trailing reduction’s loss of interior groups in the first companion pencil’s layout — its coefficients across the top block row — and expected the second companion pencil, whose coefficients run down the first block column, to keep them as the reversed route does. On the second-lowest group it does not. At four decades the first pencil’s trailing reduction returns it at $10^{-10}$ and the second pencil’s at $3 \cdot 10^{-10}$; at six, $2 \cdot 10^{-8}$ and $10^{-7}$. The reversed route returns it at $10^{-12}$ and $7 \cdot 10^{-11}$. The two trailing reductions behave alike, the second a little worse, and both are a hundred to a thousand times worse than the reversed route.

What the three routes share and do not share says where the loss is. All three invert the constant coefficient $A_0$ in some form. The reversed route inverts it as the leading block of a block-diagonal matrix, $\mathrm{diag}(A_0, I, I, I)$, whose other blocks are identities: the inversion is of $A_0$ alone, and the rest of the pencil is untouched. Both trailing reductions invert the whole $Y$ matrix of their pencil — all the coefficients but the leading one, arranged across a row in one form and down a column in the other, with the identity blocks of the companion structure off the diagonal. Inverting that matrix mixes the coefficients through the companion structure, and the mixing is what costs the interior groups digits. The layout of the coefficients does not matter; which matrix is inverted does.

That is a refinement of the earlier essay’s conclusion rather than a contradiction of it. The earlier essay found the loss was “a property of one linearisation’s layout rather than of reducing at the bottom”, having compared the trailing reduction with the reversed route on one pencil. With a second pencil to compare, the property turns out to be shared by both layouts and absent only from the reversed route, whose leading reduction inverts a block-diagonal matrix. The reversed route is not a different layout; it is a reduction that inverts less.

What the tropical roots are trusted to do #

The whole remedy leans on the tropical roots, the numbers read off the coefficients’ norms that say where each group sits before any eigenvalue is computed. An estimate that does not move tested that trust on a family whose spectrum stretched with its size and found the tropical estimate of the bottom of the spectrum steady to four per cent, where it had been said to drift. Here the groups are built to sit at the tropical roots, so the estimate is as good as it gets, and the quartic’s lesson is about what is done with it: the roots say where to scale, and a scaling paired with the wrong reduction is no better than none: at eight decades the leading reduction scaled at the second root keeps no group better than $8 \cdot 10^{-8}$, and the trailing reduction scaled at the third keeps none better than $3 \cdot 10^{-8}$. A root is an instruction about which reduction to pair it with as well as where to put it.

The measure itself deserves a sentence of caution. A backward error is computed against perturbations of every coefficient at once, and a perturbation that moves every coefficient found that the same computed answers can be stable in that sense and unstable against perturbations of the one coefficient a modeller is willing to move. Six routes to one spectrum and a backward-stable answer to a problem nobody asked made the same point about routes that are equivalent in exact arithmetic. The routes compared here are all scored on the same measure, so the ranking stands; whether a backward error of $10^{-13}$ on an interior group is small enough depends on the question the eigenvalue answers.

What the quartic says about degree #

Read across the two essays, the rule for how many routes a polynomial of degree $d$ with $d$ widely separated groups needs is not “two”, as the quadratic and the cubic suggested, and not “one per group”, as the worry about the cubic’s middle suggested. An unscaled reduction keeps the group at its end and, at a separation the cubic reached, one more beside it. Scaled at an interior root, a reduction keeps the groups within about one separation of that root on its own side. So a quartic’s four groups need two scaled reductions, at the second and third roots, and a polynomial of higher degree would need about one scaled reduction per two groups.

Polynomial eigenproblems of high degree are where this matters, because they arise as truncations of something that is not a polynomial at all — a matrix that depends on its own eigenvalue is the general case, approximated by a polynomial of whatever degree the accuracy asks for — and a polynomial fitted that way can have groups as far apart as the physics puts them. The cost of that is modest. Each reduction is one dense eigenvalue problem of $d$ times the order, and a scaling is a multiplication of each coefficient by a scalar. Four groups for the price of two eigenproblems is the same price as before; what changed is that the two must be chosen at the right roots, and the tropical roots — read off the coefficients’ norms before any eigenvalue is computed — say where those are.

What twenty quartics do not settle #

Each separation is five seeds of each family, order four; the groups are well defined because the construction makes them so, with every scalar quartic’s roots near the same four powers of ten. A polynomial whose groups are less clean, or whose tropical roots do not match its eigenvalue groups, would test whether the scaled pair still covers everything. The backward error is the measure throughout, and it is the right one for comparing routes; the forward error of an eigenvalue in an interior group depends also on its conditioning, which is not measured. The second companion form is compared on the generic family only. And eight decades between groups is a spread of twenty-four from the smallest eigenvalue to the largest — near the edge of what a double can hold in one coefficient matrix’s entries — so some of what the unscaled routes lose at eight decades may be representation rather than reduction.

Still open: a quintic, and the forward error of an interior group #

A quintic with five groups. If each scaled reduction keeps the groups within one separation of its root on its own side, a quintic’s five groups need the second root’s trailing reduction for the lowest two, the fourth root’s leading reduction for the top two, and something for the middle group at the third root. The prediction with a sign is that at six decades between groups either of the two scaled reductions keeps the middle group to $10^{-10}$, so that two still suffice at degree five, and that at eight decades neither does, so that a quintic at that separation is the first polynomial that needs three.

Forward errors in the interior. A backward error of $10^{-13}$ on an interior group says the computed eigenvalue is exact for a nearby polynomial. Whether it is close to the exact eigenvalue depends on the group’s conditioning, which for a group squeezed between two others may be large. The prediction is that on the structured family, whose exact eigenvalues are known, the interior groups’ relative forward errors under the scaled pair are within a hundred times their backward errors at every separation, so that the backward error is the number a user can rely on there too.