The second factor was the last row

A basis that has to know where the roots are took Wilkinson’s polynomial, $\prod_{i=1}^n (x - i)$, expanded it exactly in the Chebyshev basis on $[1, n]$, rounded the coefficients once to doubles and computed the roots as the eigenvalues of the colleague matrix. It was a test of a claim the roots are not the coefficients had made without measuring: that the Chebyshev basis rescues the roots the monomial basis loses. It did rescue them, by nine orders of magnitude at degree twenty. It did not stop the loss. The error still grew exponentially with the degree — $1.3 \cdot 10^{-15}$ at six, $2.8 \cdot 10^{-4}$ at forty — where a polynomial with its roots at Chebyshev points stayed at rounding to degree forty.

The essay accounted for the loss with two factors whose product sat within a factor of twenty of the measured error from degree fourteen on. One was the roots’ normwise conditioning: how far a relative change of size $u$ in the coefficient vector moves each root. The other was $\|c\|/|c_n|$, the size of the coefficient vector against its leading coefficient, which is the size of the colleague matrix’s last row against the rest of it. That second factor is not a property of the roots at all. It is a property of how the problem was handed to the eigenvalue routine, and the essay predicted, with a sign, what removing it would do.

“Diagonal balancing of the companion matrix is a standard step before its eigenvalues are computed. The prediction with a sign is that balancing the colleague matrix removes most of the second factor on the integers — bringing the error to within a factor of ten of the normwise conditioning alone at every degree from fourteen to forty — which would leave the conditioning as the only exponential.”

Both halves hold. The rest of this essay is about why they hold, and about the matrix on which the same step does nothing.

A similarity that rounds nothing #

The colleague matrix of a degree-$n$ Chebyshev series is the Chebyshev recurrence written as a matrix — halves on the sub- and superdiagonals, a one in the first row — with the coefficients $-c_j/(2c_n)$ added to its last row. Its eigenvalues are the roots. When the coefficients are much larger than the leading one, that last row is much larger than the rest of the matrix; on Wilkinson’s polynomial the ratio $\|c\|/|c_n|$ is 2.2 at degree ten, 46 at twenty and $4.4 \cdot 10^4$ at forty.

Balancing, in the form Parlett and Reinsch gave it and every eigenvalue library applies by default, replaces a matrix $C$ by $D^{-1}CD$ with $D$ diagonal, choosing each entry of $D$ to make the off-diagonal mass of its row equal to that of its column. Two details make it free. A similarity changes no eigenvalue. And every entry of $D$ is chosen to be a power of two, so that multiplying a row by it and dividing a column by it changes exponents only: no entry of the balanced matrix carries a rounding error the original did not. Whatever balancing does to the computed roots, it does by changing what the eigenvalue routine’s own rounding is relative to.

That is the whole mechanism. A backward-stable eigenvalue routine — Francis’s iteration here, the algorithm the libraries actually run — returns the exact eigenvalues of a matrix within about $u\|C\|$ of the one it was given. If $\|C\|$ is dominated by one row, the perturbation it is allowed is that row’s size spread over every entry, including the halves of the recurrence, and the recurrence entries are the ones the roots are sensitive to.

The second factor goes #

Balanced, the worst root error is within a factor of 2.4 of the conditioning at every degree from fourteen to forty: 2.4 times it at fourteen, 0.66 at eighteen, 0.70 at twenty, 0.80 at twenty-four, 0.54 at twenty-eight, 0.96 at thirty-two and 2.0 at forty. The prediction allowed a factor of ten and needed none of it. Unbalanced, the same roots are more than ten times the conditioning from degree twenty-four on, and at forty 7,000 times it.

The gain is the coefficient ratio, almost exactly. At degree forty the unbalanced error is $2.8 \cdot 10^{-4}$ and the balanced one $7.9 \cdot 10^{-8}$: three and a half thousand times smaller, against a ratio of $4.4 \cdot 10^4$ and a two-factor line that over-predicted the unbalanced error by about six. At degree twenty the gain is 4.8 against a ratio of 46. Below degree fourteen there is nothing to gain: the ratio is two or less, and the balanced and unbalanced errors are the same to the first figure.

The two ends of the range are where the balanced route sits furthest from the conditioning, and for opposite reasons. At degree fourteen the error is $8.9 \cdot 10^{-15}$, a few dozen units of roundoff, and the conditioning is smaller still: the route has reached the floor any eigenvalue computation of that size reaches, and the ratio of 2.4 measures the floor rather than the problem. At degree forty the ratio is 2.0 for the opposite reason. The worst root is no longer a small perturbation of a simple eigenvalue — it is more than a hundred billion times as sensitive as the best one — and a first-order condition number begins to under-predict what a finite perturbation does. In between, from eighteen to thirty-two, the balanced error sits slightly below the normwise line, which is what a bound that charges every coefficient its worst-case share should do on a perturbation that does not.

Where in the matrix the norm was #

The norm tells the same story from the other end. Unbalanced, the colleague matrix’s Frobenius norm tracks the coefficient ratio — 39 at degree twenty against a ratio of 46, $4.4 \cdot 10^4$ at forty against $4.4 \cdot 10^4$ — because the last row is nearly all of it. Balanced, the norm is 4.4 at degree twenty and 11 at forty: the size of the recurrence’s own halves and ones, with the last row brought down to meet them. The balancing diagonal does it with entries spanning a factor of 64 at degree twenty and $6.6 \cdot 10^4$ at forty — the ratio again, now expressed as how far apart the scales of the matrix’s first and last coordinates had to be moved.

In the language of the earlier essay’s factors, the second factor was never a property of the polynomial’s roots or of its Chebyshev coefficients as a description of them. The earlier essay showed that rounding the coefficients alone moved the roots by less than a thirtieth of the measured error from degree eighteen on; the coefficients were a faithful description. The factor belonged to the eigenvalue problem built out of them, and a diagonal change of coordinates that is exact in floating point takes it away.

Why the halves are the part that matters #

It is worth saying which perturbation the unbalanced matrix lets through, because the argument is about structure rather than size. The colleague matrix has two kinds of entry. The recurrence’s halves and the one in the first row are the same for every polynomial of degree $n$; they encode the Chebyshev basis itself. The last row encodes this particular polynomial. A perturbation confined to the last row is a perturbation of the coefficients, and the roots respond to it with exactly the conditioning the essay’s first factor measures. A perturbation of the recurrence entries is a perturbation of the basis — the matrix then describes a polynomial in a slightly different family — and nothing in the coefficients’ conditioning bounds what that does to the roots.

A backward-stable routine is free to spend its error anywhere in the matrix, in proportion to the matrix’s norm. When the last row dominates the norm, an error of $u\|C\|$ placed on a recurrence half is an error of $u\|c\|/|c_n|$ relative to that half — the coefficient ratio, applied to entries whose exactness the roots depend on. Balancing reshapes the matrix so that every row and column carries comparable mass; the routine’s error budget, still $u$ times the norm, is then a small relative change of every entry, the recurrence included. That is why the gain is the ratio and not some other function of it: the ratio is precisely the excess relative error the recurrence entries were being charged.

The condition number is an amplifier put the general version: a condition number is the largest ratio of output change to input change, and which input it is measured over is part of its definition. Measured over the coefficients, these roots’ conditioning is the first factor. Measured over every entry of the unbalanced matrix in proportion to its norm, it is the product of both. An accuracy that is a backward error makes the corresponding point about the other side of the product: a backward error means only what the norm it is stated in means.

What balancing costs #

Balancing is cheap enough that libraries apply it unasked. Each sweep visits every row and column once, $O(n^2)$ work against the eigenvalue iteration’s $O(n^3)$, and the colleague matrices here converge in one sweep at degree six, four at twenty and seven at forty. The diagonal it produces is the record of how lopsided the matrix was: on the colleague matrices it spans the coefficient ratio; on the monomial companion matrices it spans $1.8 \cdot 10^{19}$ at degree twenty and $1.2 \cdot 10^{49}$ at forty, the range of the monomial coefficients themselves. On the Chebyshev-point polynomials, whose coefficients are all alike, a single sweep finds nothing to move and the diagonal is exactly the identity.

That last fact is what makes the step safe to automate. A balancing that could make a well-scaled matrix worse would have to be applied with judgement; one that leaves a balanced matrix bit-for-bit unchanged can be applied always, and pays off on the matrices whose scaling was set by an accident of representation. Wilkinson’s polynomial in the Chebyshev basis is such a matrix. The same polynomial in the monomial basis is not, because there the representation’s accident is in the coefficients themselves, before any matrix is formed.

Root by root #

The worst-case picture hides nothing. At degree thirty-two the balanced errors follow each root’s own conditioning across the whole interval: about $10^{-15}$ at the ends, where the roots are well conditioned, rising to $2 \cdot 10^{-10}$ at the sixteenth root, where the polynomial’s humps between neighbouring roots are smallest and its slope at a root least, and falling again. The unbalanced errors have the same shape a factor of about three hundred higher. Turn the dial from twenty to forty and the gap between the two curves widens with the coefficient ratio while the balanced curve stays on the conditioning.

That is the strongest form of the prediction’s second half. With the matrix balanced, the only thing that grows exponentially is the conditioning, and it does: from $1.3 \cdot 10^{-13}$ at degree twenty to $4.0 \cdot 10^{-8}$ at forty, five and a half decades in twenty degrees. Balancing returns the routine’s accuracy to what the problem allows. It cannot return more, and the problem allows less with every degree, for the reason the earlier essay drew: equispaced roots make a polynomial whose middle is tiny next to its ends, and a root where the polynomial is tiny is a root its coefficients barely determine.

The matrix with nothing to remove #

The monomial companion matrix is the textbook case for balancing, and its coefficients are far worse scaled than the colleague matrix’s: its Frobenius norm is $2.3 \cdot 10^{19}$ at degree twenty and $1.4 \cdot 10^{49}$ at forty. Balancing brings those down to 380 and 1,500, by seventeen and forty-five orders of magnitude. The roots do not move. At degree twenty the balanced companion loses $1.7 \cdot 10^{-2}$ where the unbalanced lost $7.6 \cdot 10^{-3}$; at fourteen, $3.1 \cdot 10^{-7}$ against $7.2 \cdot 10^{-7}$. Both sit on the conditioning line, which in the monomial basis passes one — the root not determined at all — by degree twenty-four.

So the same step gains three and a half thousand times on one matrix and nothing on the other, and the difference is where each route’s error was made. In the monomial basis the roots are already as accurate as the rounded coefficients allow: the roots are not the coefficients measured the companion route’s error against the conditioning and found them equal. A backward error relative to $\|C\|$ was never the binding term, so reducing $\|C\|$ changes nothing. In the Chebyshev basis the rounded coefficients determine the roots well, and the eigenvalue routine was throwing that away by measuring its backward error against a matrix whose size was set by its last row. Balancing helps exactly where the routine, rather than the representation, was losing the digits.

Balanced is not symmetric found a third case on the Sylvester–Kac matrix, whose entries are exact integers: balancing divided every eigenvalue condition number by about sixty and left their growth with the order untouched. It is the same statement read from the matrix side, and a condition number for one eigenvalue is the quantity both were measuring. Balancing changes a constant; the growth belongs to the problem.

A matrix already balanced #

The control behaves as it should. With roots at the Chebyshev points of $[1, n]$ the polynomial’s Chebyshev coefficients are all of comparable size, the colleague matrix’s last row is no larger than the recurrence, and balancing leaves it nearly or exactly alone. The root errors balanced and unbalanced agree to every printed digit at every degree, at rounding throughout — $4 \cdot 10^{-15}$ at degree six, $9 \cdot 10^{-14}$ at forty. A preprocessing step that does nothing where there is nothing to do is the cheapest kind, and it is why libraries can apply this one without asking.

What degrees six to forty do not show #

Every measurement here uses one polynomial family, two root distributions and Francis’s iteration on a dense matrix. The balancing is the classical one, which equalises row and column sums; other norms and other scalings exist and would be expected to behave alike on a matrix this lopsided, which is not tested. The conditioning used is normwise in the coefficient vector, the measure the colleague matrix’s backward error is stated in; a structured analysis that kept the recurrence’s entries exact and perturbed only the last row would predict a smaller error, and the balanced route sits slightly below the normwise line at several degrees, which may be that effect and is not separated here. And the monomial companion’s coefficients are formed in double precision by repeated multiplication rather than rounded once from exact values, so its curve here and the earlier essay’s differ in the last digit from degree eighteen on.

The scaling that buys ten orders found the same kind of free repair for a quadratic eigenvalue problem — a change of variable exact in both directions that brought back every digit a bad choice of units had cost — and a condition number scaling cannot move found where such repairs stop. Both have the shape this one has: a scaling recovers what the representation lost, and nothing the problem itself withholds.

Still open: an adapted basis, and the structured bound #

A basis built for equispaced roots. With the second factor gone, the exponential is the conditioning, and the conditioning belongs to the basis as much as to the roots. Orthogonal polynomials on the equispaced points $1, \dots, n$ — the discrete Chebyshev, or Gram, polynomials — are to the integers what Chebyshev polynomials are to Chebyshev points. The prediction with a sign is that Wilkinson’s polynomial expanded exactly in the Gram basis, with its roots taken from the corresponding balanced comrade matrix, keeps every root to within a hundred times the unit roundoff to degree forty, and that the roots’ normwise conditioning in that basis grows by less than two decades across the same range.

The structured bound. If the balanced error is the colleague matrix’s backward error with only the last row perturbed, it should be predicted by a conditioning that perturbs the coefficients alone and leaves the recurrence exact. The prediction is that this structured conditioning times u lies within a factor of three of the balanced route’s worst error at every degree from fourteen to forty, where the normwise line is off by up to a factor of 2.4, and that the two differ most at the degrees where the balanced route sits below the normwise line.