Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Companion form — where it appears

The matrix whose characteristic polynomial is a given one, built from its coefficients in a single row with an identity below. Computing roots as its eigenvalues is what every library does, and the computation is backward stable for the matrix rather than for the polynomial.

Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.

00.0939569-2-1.24498-0.4899610.2650581.020081.7751real partimaginary parttwo routes, one spectrumeigenvalues16rows8complex16against the closed form2.1·10⁻¹⁵n rows and 2n eigenvaluesso the eigenvectors are not a basis

A matrix that depends on its own eigenvalue

A damped structure does not produce Ax = λx. It produces (λ²M + λC + K)x = 0, where the matrix whose null vector is wanted is a function of the number being solved for — so there is nothing to factorise, an n × n problem has 2n answers, and the eigenvectors cannot be a basis.

polynomial · Polynomial eigenvalue first · leading5.47·10⁻⁶first · trailing4.62·10⁻⁵second · leading4.27·10⁻⁵second · trailing2.23·10⁻⁴symmetric · leading5.47·10⁻⁶symmetric · trailing4.05·10⁻⁵all six are the same algebrabest route5.5·10⁻⁶worst route2.2·10⁻⁴spread across the six41condition of the linearisation8.3·10¹²the spectra agreeand the arithmetic does not

Six routes to one spectrum

Three linearisations of one quadratic, each reduced to a standard eigenvalue problem two ways. All six have exactly the same eigenvalues in exact arithmetic. On a well-scaled problem they differ by noise; on a badly scaled one by a factor of forty; and two of the six are the same matrix.

polynomial · Linearisation backward error 263850627410⁻⁵10⁻³10⁻¹rows in the linearisation‖g − r‖ on the target setpolynomialrationalequal cost, two basesreach0.06largest size drawn78rational there2·10⁻⁵polynomial there0.0015the ratio73no winner on an easy targetand two orders on a hard one

Two approximants and one matrix size

A polynomial approximant linearises to nd rows and a rational one to n(m+1), so the fair contest fixes the matrix and varies the basis. On an easy target set the two are indistinguishable and the ordering flips with the noise; on one that reaches a branch point the rational pulls away by two orders.

polynomial · Approximant choice 57911131517192110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²degreerelative error of the worst rootmeasuredκ × ua polynomial is its coefficientsworst root, measured0.0076predicted, κ × u0.0023root condition number10¹³largest coefficient1.4·10¹⁹the roots are integersand the coefficients are not the roots

The roots are not the coefficients

A polynomial whose roots are the integers one to twenty, expanded exactly, handed to the routine every library uses. The computed roots are wrong in the third digit, the computation is backward stable for the matrix it factorised, and above degree eighteen the coefficients are not double-precision numbers at all.

error · Conditioning 012345610⁻¹10²10⁵10⁸10¹¹log₁₀ γ, the change of unitscondition numberthe linearisationthe quadraticone problem, two amplifiersκ(quadratic), first6.6κ(quadratic), last6.6κ(linearisation), last10¹²how far the first moved1the problem is as well conditioned as everand the method is not

The number that moves when the problem does

Two quantities are offered as the condition number of one eigenvalue. One is unmoved to eight digits by a change of variable that is exact in both directions, and grows like the square root of the chain's length. The other is inflated by ten orders by that change of variable, and is ten times too large before anything has been done at all.

polynomial · Linearisation backward error 1e-161e-121e-81e-41e0worst backward error over the groupleading reductiontrailing reductionscaled at the middle root, leadingscaled at the small root, leadingsmall groupmiddle grouplarge groupsmall groupmiddle grouplarge groupsmall groupmiddle grouplarge groupsmall groupmiddle grouplarge groupdots: worst over five cubicsthe middle group comes with the large one

The middle group needs no reduction of its own

A quadratic whose two groups of eigenvalues sit far apart needs two reductions, one per end. A cubic can have three groups, and the middle one is inverted by neither reduction, so the worry was that it would need a third route — a shift-and-invert at the middle tropical root. Build order-four cubics with three groups up to eight decades apart and measure every eigenvalue: the leading reduction keeps the middle group at 10⁻¹¹ or better at every separation, the trailing reduction loses it to 5·10⁻⁹ by eight decades, and the reversed polynomial's leading reduction, which inverts the same constant coefficient as the trailing one, keeps it at 2·10⁻¹⁴. The middle group's loss belongs to the pencil, not to the end. Two reductions still give all twelve eigenvalues to 2·10⁻¹¹. And the tropical scaling at the small root, which rescues the small group when every coefficient shares one diagonal form, does nothing for it once the coefficients are perturbed out of that form.

polynomial · Polynomial scaling 612182430364210⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1degree nworst relative root errormonomial, integersmonomial, Chebyshev pointsChebyshev, integersChebyshev, Chebyshev pointsred: monomial; blue and green: Chebyshevthe basis has to match the roots

A basis that has to know where the roots are

Wilkinson's polynomial loses its roots in the third figure at degree twenty when they are computed from its monomial coefficients, and the repair offered was to change the basis: in Chebyshev coefficients, with the colleague matrix, the conditioning 'does not degrade exponentially with degree'. Expanded exactly in that basis and rounded once, the integers' roots come back ten orders better at degree twenty — 4.4·10⁻¹³ against 7.6·10⁻³ — and still degrade exponentially, at a third of a decade a degree, to 2.8·10⁻⁴ at forty. Place the same number of roots at the interval's Chebyshev points instead and they stay at 10⁻¹⁴ at every degree, while the monomial route loses them as fast as the integers. The basis does not repair the problem; it has to match where the roots are.

error · Conditioning

Named alongside it

The objects these essays reach for when they reach for this one.

Backward errorCondition numberLinearisationMatrix polynomialChebyshev basisExact ground truthQuadratic eigenvalue problemScalingCharacteristic polynomialWilkinson polynomialApproximation before linearisationAsymptotic analysis

All concepts