The middle root has no neighbour to lean on

An interior root needs its own scaling followed a family of matrix polynomials up in degree. A quadratic with two groups of eigenvalues far apart needed two reductions of its companion pencil, one per group; a cubic’s middle group, unexpectedly, needed none of its own; and a quartic’s four groups, up to eight decades apart, were all kept by two reductions once each was scaled at the right tropical root — the trailing reduction scaled at the second root for the lower two groups, the leading reduction scaled at the third for the upper two.

Its last section asked what a fifth group does. “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.”

The first half of that holds and the second half is not the question. The pair keeps the outer four, and it never keeps the middle.

Thirteen ways to reduce one pencil #

The quintics are built as the quartics were. Each is $P(\lambda) = \sum_{k=0}^{5} A_k\lambda^k$ with $4 \times 4$ coefficients $U\,\mathrm{diag}(c_k)\,V^{\mathsf T}$, where the four diagonal entries are scalar quintics whose roots sit near $10^{-2a}$, $10^{-a}$, $1$, $10^{a}$ and $10^{2a}$, so the twenty eigenvalues come in five groups of four, $a$ decades apart. The generic family adds to each coefficient an independent random matrix of three tenths of its norm, which keeps the groups and destroys the diagonal structure. Five seeds each, at $a = 2, 4, 6$ and 8.

The tropical roots are read off the coefficients’ norms, $\tau_k = \|A_k\|/\|A_{k+1}\|$, and they sit at the five groups. Every eigenvalue is assigned to a group by the geometric midpoints between consecutive tropical roots and scored by its backward error as an eigenvalue of $P$. The pencil is the first companion form, a $20 \times 20$ pair $\lambda X + Y$ whose first block row holds the coefficients. A reduction turns it into an ordinary eigenvalue problem by inverting one side: the leading reduction inverts $X$, which holds $A_5$; the trailing reduction inverts $Y$, which holds $A_0$. Each can be done on the polynomial as given or after scaling $\lambda = \tau_k\mu$ at any of the five tropical roots, which makes ten routes and two unscaled ones; six routes to one spectrum is where this family of routes was first laid side by side. A thirteenth inverts neither end and is described below.

At six decades the map is a staircase for the outer groups. The lowest group is kept by every trailing reduction scaled at or below the middle root and by the unscaled trailing reduction; the second only by the trailing reduction at the second root; the fourth only by the leading reduction at the fourth root, or on the structured family also by those centred lower; the top by every leading reduction scaled at or above the middle. That is the quartic’s pattern, one group further out at each end. The middle column is nearly empty: on the structured family two routes keep it, the unscaled leading reduction and the leading reduction at the third root; on the generic family none does.

The predicted pair, and the middle it misses #

The prediction named two routes and asked them to keep all five groups between them.

On the outer four they do what the quartic’s pair did. The lowest group comes back at $10^{-15}$ at every separation, the second at $5 \cdot 10^{-13}$ to $6 \cdot 10^{-12}$ from four decades, the fourth at $8 \cdot 10^{-14}$ to $10^{-11}$, the top at $10^{-15}$ — until eight decades, where the top group is lost by every route on both families. To six decades the prediction’s pair is exactly the quartic’s pair moved out by one root.

The middle group is another matter. The trailing reduction at the second root returns it at $10^{-9}$ at two decades and at $10^{-2}$ to $2 \cdot 10^{-1}$ from four; the leading reduction at the fourth root at $4 \cdot 10^{-9}$ to $2 \cdot 10^{-8}$ at two decades and $7 \cdot 10^{-2}$ or worse from four. Neither keeps it to $10^{-10}$ at any separation, on either family. The prediction expected them to hold the middle to six decades and lose it at eight; they lose it from the start, and by four decades they return eigenvalues for it that are no eigenvalues of the polynomial at all.

Both ends shrink at once #

Why the pair fails is visible in the coefficients before any eigenvalue is computed. Scaling at a tropical root makes the two coefficients that meet there the largest, and pushes every other one down by its distance from the root. At an outer root that leaves one end of the pencil large and the other tiny, and the reduction that inverts the large end is well conditioned. At the middle root it does something different.

Scaled at the middle root, $A_2$ and $A_3$ are the largest and both ends fall together: $A_0$ and $A_5$ are each $10^{-6}$ of the largest at two decades, $10^{-12}$ at four, $10^{-18}$ at six and $10^{-24}$ at eight — ten to the minus three times the separation, on both sides. Compare the roots the pair is scaled at. At the second root the trailing reduction inverts the block holding $A_0$, and there $A_0$ is $10^{-a}$ of the largest — $10^{-4}$ at four decades, $10^{-6}$ at six — while $A_5$ is $10^{-6a}$; at the fourth root the leading reduction inverts $A_5$ at $10^{-a}$ while $A_0$ is $10^{-6a}$. Each of the pair stands one separation from the end it inverts and five from the other. At the middle root both ends are three separations away. Inverting a small block is not itself the trouble — the block here is a scaled orthogonal matrix and inverts exactly — but the reduced matrix then has a norm $10^{3a}$ times the middle group’s size, and an eigensolver’s error is a few units of roundoff of that norm: at four decades, $10^{-4}$ of a middle eigenvalue, at six, more than all of it. A reduction scaled anywhere else is centred on another group and reaches the middle across even more. The quartic never met this: its two interior roots each have one large neighbour on the side away from the middle, and the quartic’s interior groups could lean on it. A quintic’s middle root has two equal neighbours and no outer one to lean on.

The middle group needs no reduction of its own found the cubic’s middle group kept by the leading reduction, because at three groups the middle root’s distance to the top was one separation and the leading reduction could reach it. At five groups the distance is two separations each way, and the measurement says that is too far for a pencil reduced from either end.

Two routes, but not those two #

On the structured family a route centred on the middle does keep it. The leading reduction scaled at the third root returns the middle group at $10^{-13}$ at two decades, $2 \cdot 10^{-12}$ at four and six, and $8 \cdot 10^{-13}$ at eight; the unscaled leading reduction does the same, because the middle root here is near one. And the same route keeps the fourth and top groups too.

So the structured quintic needs two routes at four and six decades after all: the trailing reduction at the second root for the lower two groups and the leading reduction at the middle root for the upper three. Not the predicted two — the prediction’s leading reduction at the fourth root keeps the upper pair but not the middle, and the middle root’s leading reduction keeps all three. At eight decades the same two keep four groups and the top group is kept by none. The prediction’s “first polynomial that needs three” is the right count for the wrong reason: what makes two enough or not is whether the upper route is centred on the middle, not the separation.

On the generic family nothing is centred well enough. At four and six decades no route of the thirteen keeps the middle group: the middle root’s own leading reduction returns it at $4 \cdot 10^{-2}$ and $5 \cdot 10^{-2}$, where the same route on the structured family returned $2 \cdot 10^{-12}$. The measurement shows the difference and does not explain it. One reading fits the numbers: the structured quintic’s reduced matrix, for all its $10^{3a}$ norm, is graded — its large entries sit in the block that holds the large coefficients, in a pattern the Francis iteration’s deflation can follow — and graded matrices are the case where an eigensolver beats its own normwise error bound by many digits. The generic family’s random parts put a few per cent of every coefficient into every entry, which is exactly what removes grading. That is a reading, not a measurement. The generic family’s random parts couple the groups through every coefficient, and whether that makes the middle group’s eigenvalues worse conditioned or only harder to reach by a reduction is the next question rather than this one’s answer. A perturbation that moves every coefficient is the reminder that the backward error reported here is of that unstructured kind: it lets every coefficient move, and it is small or large for the polynomial as a whole.

For a code that has to choose its routes from the tropical roots alone, before any eigenvalue is computed, the map offers no single rule. On the structured family, centring the upper route on the middle root rather than the fourth keeps every group to six decades with two reductions. On the generic family the same choice is worse than the prediction’s: the middle root’s leading reduction returns the fourth group at $10^{-7}$ at four decades and $6 \cdot 10^{-2}$ at six, where the fourth root’s kept it at $10^{-13}$ and $10^{-11}$, and it keeps the middle no better. There the predicted pair is the best pair available and still leaves the middle group to something that is not a reduction from an end.

A reduction that inverts neither end #

The thirteenth route was built to test the reading. Write the pencil as $(\lambda - \sigma)X + (Y + \sigma X)$ and invert the combination $Y + \sigma X$, which holds every coefficient and is well conditioned wherever $\sigma$ is not an eigenvalue: the eigenvalues $\nu$ of $(Y + \sigma X)^{-1}X$ give $\lambda = \sigma - 1/\nu$. It is the shift-and-invert step of every sparse eigensolver, applied once. Scaled at the middle root, with $\sigma$ one unit to the side away from the middle group’s four eigenvalues, it inverts neither end.

It keeps the middle group at $2 \cdot 10^{-15}$ at two decades and $10^{-15}$ at eight on the generic family, where no reduction from an end keeps it; and at two, four and eight on the structured family. It fails on the generic family at four and six decades, at $6 \cdot 10^{-2}$ and $3 \cdot 10^{-2}$, and on the structured at six. So it is not a cure, and its failures fall where the plain reductions fail too; but it is the only route that ever keeps the generic middle group, which says the obstacle at eight decades was the inversion of an end and not the group itself. The number that moves when the problem does priced a backward error that is a property of the route rather than of the polynomial; the middle group’s is one of those.

What the prediction carried over #

The scaling that buys ten orders introduced tropical scaling as the device that equalises the two coefficients a group of eigenvalues depends on, and every essay since has used it to choose where to centre a reduction. This one finds its limit at the middle of an odd number of groups: the scaling does equalise the middle two coefficients, and equalising them is no help to a reduction that has to invert something else.

The prediction treated the quintic as the quartic with one more group, and asked how far the quartic’s two routes would stretch. That was the right question for the four outer groups, and they stretch exactly as far as the quartic’s did, to six decades and through eight for three of them. For the middle group it was the wrong frame. The quartic’s routes each served a pair of groups that shared a side of the spectrum; the quintic’s middle group shares a side with neither pair, and a route centred on an outer root reaches it only across the full width of the coefficients’ range. Two groups need two reductions found the same thing at degree two, where the two groups were the two ends: a group is kept by the route centred on it, and the cubic’s exception was that its middle root was near enough to an end.

A backward-stable answer to a problem nobody asked is the warning that applies to the generic family’s middle group at four and six decades: every route returns twenty eigenvalues, the pencil’s backward error is small for each of them, and four of them are not eigenvalues of the polynomial to better than a few per cent. The grouping and the polynomial’s own backward error are what say so.

What ten quintics do not show #

Five seeds a family and four separations make a map, not a law, and the map’s corners are noisy: at two decades the groups crowd each other and the midpoint grouping misplaces some eigenvalues, which is why the generic family’s second group shows as kept by no route there, and the shifted reduction’s failures at four and six decades may owe as much to where $\sigma$ lands as to anything about the middle group. The structured and generic families differ in more than one way at once. At eight decades the top group is lost by every route on both families, the leading reduction scaled at its own root included, at backward errors of a few tenths; the coefficients’ norms there run from about 2 at both ends to $7 \cdot 10^{24}$ in the middle, and the top group sits sixteen decades above the middle root. Whether that loss is the reductions’, the backward error’s own evaluation at $|\lambda| \approx 10^{16}$, or the group’s, is not settled by anything here, and it is the one result in the map that the essays before this one would not have predicted either. And the reductions here are all to ordinary eigenvalue problems; the QZ algorithm, which works on the pencil without inverting either side, is the route a library would use, and it is not measured.

Still open: the generic middle, and the pencil whole #

Conditioning or reach. The generic middle group is lost by every reduction at four and six decades. The prediction with a sign is that its eigenvalue condition numbers, computed from left and right eigenvectors of $P$ at the eigenvalues the structured route would return, are within a factor of a hundred of the structured family’s — so that the loss is the reductions’ reach and not the group’s sensitivity, and a route that does not invert an end would keep it at every separation.

The pencil whole. The QZ algorithm on the scaled pencil inverts nothing. The prediction is that one QZ run on the pencil scaled at the middle root keeps all five groups of the structured quintic to $10^{-12}$ at every separation up to six decades, and the generic quintic’s four outer groups and its middle one, so that at degree five the number of routes needed is one, and the count that grew from one to two between the quadratic and the quartic was a property of reductions rather than of polynomials.