The middle group needs no reduction of its own

Two groups need two reductions pulled the eigenvalues of a quadratic apart until its two tropical roots stood twenty-three decades from each other, and found that no scaling kept the small group. What kept it was the other reduction of the same companion pencil: invert the constant coefficient instead of the leading one, and the small eigenvalues come back at rounding while the large ones are lost instead. Each reduction is exact at its own end, so the two together give the whole spectrum. The essay closed on the case that would say how far that reaches. A cubic matrix polynomial $P(\lambda) = A_3\lambda^3 + A_2\lambda^2 + A_1\lambda + A_0$ can have three tropical roots, and so three groups of eigenvalues. Two reductions see two ends. The middle group is the one neither inverts.

The natural guess, and the one written down there, is that the middle group is lost by both — that a reduction is accurate near the coefficient it inverts and degrades with distance from it, so that a group sitting between the ends is far from both. If that were so, the remedy would need a third route for every interior group: a shift to the middle tropical root and an inversion there, which is a different eigenproblem for each group and a cost that grows with the degree. A quartic would need four solves, a polynomial of degree ten up to ten.

The figure at the top answers it at the widest separation measured. It is the worst backward error over each group, over five cubics, for four routes, and the middle group under the leading reduction is at $6\cdot 10^{-14}$. It is not lost. It comes with the large group.

Three groups, built to order #

The cubics are order four, so each has twelve eigenvalues — $nd$ of them for order $n$ and degree $d$, more than the matrix has rows, which is the oddity a matrix that depends on its own eigenvalue began from. Each coefficient is $U\,\mathrm{diag}(c_k)\,V^{\mathsf T}$ for one pair of random orthogonal matrices $U$ and $V$, and the $i$-th diagonal entries of $A_3, \dots, A_0$ are the coefficients of a scalar cubic with three real roots: one near $10^{-a}$, one of size about one, and one near $10^{a}$, each slightly different for each $i$ so that no eigenvalue is repeated. That puts four eigenvalues in each of three groups, $a$ decades apart, and their exact values are known.

The norms of the coefficients then fall into the shape the tropical roots read. At $a = 6$ the four Frobenius norms are about 7, $3.9\cdot 10^6$, $2.8\cdot 10^6$ and 2 for $A_0$ to $A_3$, and the three corners of the max-plus polynomial $\max_k(\log\lVert A_k\rVert + kx)$ — the tropical roots, $\lVert A_{k-1}\rVert/\lVert A_k\rVert$ for consecutive pairs when they are increasing — are $1.7\cdot 10^{-6}$, $1.4$ and $1.4\cdot 10^6$. Each predicts the size of one group to within a factor of two.

A family built this way has a property no problem from an application has: every coefficient is diagonalised by the same two transformations, so the matrix polynomial is four scalar cubics in disguise. That will turn out to matter, so there is a second family, called generic below: the same coefficients with an independent random matrix added to each, of three tenths of that coefficient’s norm. The groups and the tropical roots survive almost unchanged — the generic cubic at $a = 6$ has norms 8, $4.3\cdot 10^6$, $2.8\cdot 10^6$ and 2.1, and roots $1.8\cdot 10^{-6}$, $1.5$ and $1.3\cdot 10^6$ — but the common diagonal form is gone, and with it the exact eigenvalues. What is measured is therefore the backward error of each computed $\lambda$, the smallest singular value of $P(\lambda)$ over $\sum_k |\lambda|^k\lVert A_k\rVert$, which a perturbation that moves every coefficient used as its measure and needs no reference answer.

The linearisation is the first companion pencil, the one six routes to one spectrum began with: $\lambda X + Y$ with $A_3$ and two identity blocks on the diagonal of $X$, and $A_2$, $A_1$, $A_0$ across the top of $Y$ with two negative identities below. The leading reduction forms $-X^{-1}Y$ and finds its eigenvalues; the trailing reduction forms $-Y^{-1}X$, whose eigenvalues are $1/\lambda$. Both are a twelve-by-twelve standard problem solved by the same Francis iteration, and both are exact in the sense the problem the solver was actually given drew for linearisations: same eigenvalues, same multiplicities, every loss committed by the arithmetic. Each group is whatever falls between the geometric midpoints of consecutive tropical roots.

The ends behave as they did #

The outer groups repeat the quadratic. On the generic family the large group under the leading reduction stays at about $10^{-15}$ at every separation, and so does the small group under the trailing reduction. Each is lost under the other: the small group under the leading reduction climbs from $10^{-13}$ at two decades to $5\cdot 10^{-11}$ at four and $7.6\cdot 10^{-2}$ at six, and the large group under the trailing reduction mirrors it to $3.5\cdot 10^{-1}$ at eight. Two decades at a time, the wrong reduction gives up about as many digits as the separation has decades and then all of them.

The middle group does not follow either pattern. Under the leading reduction it reads $8.5\cdot 10^{-14}$, $3.3\cdot 10^{-14}$, $2.0\cdot 10^{-11}$ and $6.4\cdot 10^{-14}$ at the four separations: no trend. Under the trailing reduction it is as good to six decades and then worse, $4.5\cdot 10^{-9}$ at eight. The badge records the worst of each over the whole sweep. The leading reduction, inverting the coefficient of the large end, is the one that keeps the middle.

Turn the dial to the structured family and the same three facts hold with gentler numbers. The small group under the leading reduction is lost more slowly there — $1.2\cdot 10^{-7}$ at six decades and $8.4\cdot 10^{-6}$ at eight, where the generic cubic has already lost every digit — but the middle group is again flat under the leading reduction and rising under the trailing one, to $1.3\cdot 10^{-9}$.

One number in the sweep is not a route’s. At six decades the middle group reads between $1.6\cdot 10^{-11}$ and $4.6\cdot 10^{-11}$ under the leading reduction, the trailing reduction, the reversed route described below and both scalings at the middle root, on both families, and at four and eight decades the leading reduction is back near $10^{-13}$. A loss that every reasonable method shares at one separation and none at the next belongs to the five cubics drawn there rather than to any reduction; most likely two middle eigenvalues of one of them sit close enough to be sensitive. It is not chased here, because it does not distinguish anything.

Where each eigenvalue lands #

Taking one cubic apart shows the groups as clusters rather than worst cases. The three dashed lines are the tropical roots, $1.8\cdot 10^{-6}$, $1.5$ and $1.3\cdot 10^6$, and each has four eigenvalues gathered around it. At the right, the leading reduction’s four large eigenvalues are at $10^{-16}$ and the trailing reduction’s are strung up the axis to $7\cdot 10^{-3}$. At the left the picture reverses: the trailing reduction’s small eigenvalues are at $10^{-16}$, and the leading reduction’s reach $3\cdot 10^{-2}$. Two of the small eigenvalues are a complex pair under the trailing reduction and come out real, at the wrong size, under the leading one.

In the middle the two reductions sit together, between $2\cdot 10^{-12}$ and $2\cdot 10^{-11}$. Nothing in the middle cluster is lost by either at this separation; it is at eight decades that the trailing reduction’s middle rises off the floor. Neither reduction is at $10^{-16}$ on the middle group, and that is part of the answer: the middle eigenvalues are computed to about the accuracy their own problem allows, by both routes, until one of the routes starts to cost something extra.

The same inversion in another pencil #

The obvious reading of the trailing reduction’s late loss is the one the guess began from: it inverts the constant coefficient, the middle group is on the far side of that coefficient from the small end, and distance from the inverted end costs digits. That reading has a test. Reverse the polynomial — write $\lambda^3 P(1/\lambda) = A_0\lambda^3 + A_1\lambda^2 + A_2\lambda + A_3$ — and take the leading reduction of the reversed polynomial’s companion pencil, then invert the eigenvalues it returns. That route also inverts $A_0$. It reaches the small group the same way the trailing reduction does. What differs is only where the identity blocks of the pencil sit relative to the inverted coefficient.

The reversed route keeps the middle group exactly as the leading reduction does: $2.2\cdot 10^{-14}$ at eight decades on the generic family, against $4.5\cdot 10^{-9}$ for the trailing reduction of the original pencil — a factor of two hundred thousand between two routes that invert the same matrix. It keeps the small group at rounding too, and it loses the large group as the trailing reduction does. So the trailing reduction’s cost on the middle group is not a property of inverting $A_0$. It belongs to the particular companion pencil, in which inverting $Y$ means inverting a matrix that holds $A_2$, $A_1$ and $A_0$ in one block row beside two identities of size one. At eight decades that block row has norm $10^{8}$ against identities of norm one, and its inverse is computed with the corresponding imbalance. The reversed pencil puts $A_0$ alone on the block diagonal of the matrix it inverts, and the imbalance is not there.

That is the same lesson six routes to one spectrum drew from a quadratic in bad units — that linearisations with identical eigenvalues are not interchangeable in floating point, and that the difference is in which matrix gets inverted beside what — but at a scale where it decides a whole group. For the remedy it is good news: the small end has two routes, one of which costs the middle group nothing.

The scaling that worked only on the easy family #

The other device for separated groups is tropical scaling: put $\lambda = \tau\mu$ at one tropical root $\tau$ and divide every coefficient by the largest $\tau^k\lVert A_k\rVert$, so that the group near $\tau$ becomes a group near one in a problem with balanced coefficients. The scaling that buys ten orders showed what one such scaling does for a quadratic in bad units. For separated groups the remedy proposed is one scaling per root, keeping from each run the group its root predicts — the same structure as two reductions, with the scaling doing the work the choice of reduction does here.

On the structured family it works. Scaled at the small root, the leading reduction keeps the small group at $7\cdot 10^{-13}$ or better at every separation, where unscaled it had reached $8.4\cdot 10^{-6}$. On the generic family it does not: from four decades on, the scaled run is at $7.4\cdot 10^{-2}$ and by eight at $3.0\cdot 10^{-1}$, worse than the unscaled run’s $7.3\cdot 10^{-2}$. At eight decades it also stops returning four eigenvalues in each group, which the figure’s worst-case cannot show and the sweep records.

The reason is the property the generic family was built to remove. When every $A_k$ is $U\,\mathrm{diag}(c_k)\,V^{\mathsf T}$, the scaled pencil is the unscaled pencil in different units for every one of the four scalar cubics at once, and a change of units is something a stable reduction respects. Perturb the coefficients by three tenths of their norm and the scaling no longer acts on a hidden diagonal problem. At eight decades and $\tau \approx 10^{-8}$ it leaves $A_0$ and $A_1$ of order one, $A_2$ of order $10^{-8}$ and $A_3$ of order $10^{-24}$, and the leading reduction still inverts the last of these — the smallest matrix in the problem, now with perturbations from the other three that no longer line up with its own structure. Scaling cannot change which coefficient a reduction inverts. It can only make it look well balanced when the coefficients happen to commute with one another’s structure.

This is the same verdict two groups need two reductions reached on a quadratic chain, where the scaling at the small root made the small group worse, and it says something about where to test such a claim. A family assembled from scalar polynomials passes it. The number that moves when the problem does separated a condition number that is invariant under a change of variable from one that is not; a diagonal family is the case in which every scaling is a change of variable, and the generic one is the case in which it is not.

Two reductions are still enough #

Put together, the remedy is the quadratic’s with one assignment added: take the large and middle groups from the leading reduction, the small group from the trailing one, and every eigenvalue comes back with backward error at most $2.0\cdot 10^{-11}$ on both families at every separation — and that maximum is the six-decade middle-group number every route shares. At two, four and eight decades the worst over twelve eigenvalues is below $10^{-12}$.

The best single route, chosen per separation and family with hindsight, stays within three orders of the combination while the groups are at most four decades apart — $4.5\cdot 10^{-11}$ against $3.3\cdot 10^{-14}$ at four — and is catastrophically worse after: on the generic family $2.4\cdot 10^{-2}$ at six decades and $7.3\cdot 10^{-2}$ at eight. On the structured family a single route survives — the scaling at the small root keeps the small group, and the leading reduction already keeps the others — which is the diagonal family’s flattery again.

So the cubic costs two reductions, the same as the quadratic. The worry that a polynomial of degree $d$ needs $d$ solves, one per group, does not survive the first case beyond two groups. And the remedy has one decision in it rather than three: which groups to read from the leading reduction. The tropical roots answer it for free, since they say where each group is before anything is solved, which is what an estimate that does not move found them good for — locating groups, not sizing the smallest eigenvalue.

What does not explain it #

The measurements say the middle group is kept by the leading reduction and by the reversed polynomial’s leading reduction, and lost late by the trailing reduction of the original pencil. They do not say why the leading reduction is accurate there, and the argument that comes first to hand predicts the opposite.

That argument runs as follows. The Francis iteration is backward stable for the matrix it is given, so the computed eigenvalues of $-X^{-1}Y$ are exact for a perturbation of relative size about $u$, and $\lVert X^{-1}Y\rVert$ is of the order of the largest tropical root, $10^{a}$. An eigenvalue of size one then moves by about $u\cdot 10^{a}$, and since $P'(\lambda)$ near the middle group is of the size of $\lVert A_2\rVert$, which also dominates the yardstick $\sum_k|\lambda|^k\lVert A_k\rVert$, the backward error should be about $u\cdot 10^{a}$ too: $10^{-8}$ at eight decades. The measurement is $6\cdot 10^{-14}$.

So whatever keeps the middle group is not the size of the perturbation but its shape. The error the reduction commits is far from the worst normwise perturbation of its size, and the middle eigenvalues are insensitive to the part it does commit — the same distinction between a bound and an error that a backward-stable answer to a problem nobody asked found between the matrix that was solved and the problem that was posed. Saying what that shape is would take a structured perturbation analysis of the companion pencil, and this essay does not have one. The verdict rests on the measurements, each of which was also checked against a deliberately wrong version of itself, not on an explanation.

What four by four does not show #

Order four, real roots by construction, one linearisation, a Francis iteration on a standard problem, and two families built from one diagonal form. The tropical scalings were designed for an algorithm that works on the pencil without inverting either coefficient, and that is not measured here; nor is a cubic whose groups have different numbers of eigenvalues, which happens whenever a coefficient is singular or nearly so. The five seeds at each separation are enough to see a rate and not enough to describe a distribution.

Still open: a quartic, and the second companion form #

A quartic with four groups. 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.

The second companion form. The trailing reduction’s cost on the middle group was traced to the block row it inverts. 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.