Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Quadratic eigenvalue problem — where it appears

The problem a damped structure produces instead of Ax = λx, with the matrix a quadratic in the eigenvalue. A problem of size n has 2n eigenvalues and n components, so the eigenvectors cannot be independent and nothing in the eigenbasis picture survives.

Named by 16 essays across 4 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 0246810⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹log₁₀ γ, the change of unitsrelative errorforward errorη, the quadraticη, the linearisationagainst a closed formη(linearisation), worst7.6·10⁻¹³η(quadratic), worst1.2·10⁻⁴forward error, worst0.0013coefficient spread4.2·10¹⁵the solver is right at every stopabout a problem nobody asked

A backward-stable answer to a problem nobody asked

One quadratic eigenvalue problem, in nine systems of units, with a change of variable that is exact in both directions. The residual the solver prints stays at the rounding level at every stop. The answer loses eleven orders of magnitude, and the two facts are consistent.

polynomial · Linearisation backward error 0246810⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹log₁₀ γ, the change of unitsforward erroras writtenafter scalingone change of variableunscaled, worst0.0013scaled, worst1.7·10⁻¹³orders recovered10scaled coefficient spread4.5the answer was never the problemthe units were

The scaling that buys ten orders

Two lines computed from three norms, a change of variable that is exact in both directions, and the whole of the loss the previous essay measured comes back — flat, at every stop, because after scaling every stop is the same problem.

polynomial · Polynomial scaling 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 -33-28.2505-23.5009-18.7514-14.0018-9.25229-4.502750eigenvalueQ(μ) ≺ 0one Cholesky, two answersabove the certificate8below it8the gap0.67critical β for this n5.8the spectrum is real by classnot by outcome

Every eigenvalue real, and a test that says so

A quadratic eigenvalue problem has no reason to have real eigenvalues. One class does, as a property rather than an outcome, and the proof is a Cholesky that completes. The boundary of the class has a closed form, and at the boundary the arithmetic loses half its digits with nothing ill conditioned anywhere.

polynomial · Hyperbolic quadratic -5-3.20611-1.412210.3816782.175573.969460log₁₀ |λ||λ| = 1λλ′ = 1, in the algebrapairs6decades of spectrum9.6pairing error, general3.3·10⁻⁹pairing error, structured2.2·10⁻¹⁶a symmetry the solver never knew aboutand the half of the answer it decides

A spectrum that comes in reciprocal pairs

A palindromic quadratic reads the same backwards, so λ is an eigenvalue exactly when 1/λ is. A general solver discards that, computes the large half of the spectrum perfectly and the small half to seven digits — and the small half is a division away from being perfect too.

polynomial · Structured spectrum 1357910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴log₁₀ b, the couplingrelative errorsmall half, directstructure-preservingsmall half, by 1/λone divisionlarge half, direct5.5·10⁻¹⁵small half, direct10⁻⁷small half, by 1/λ4.9·10⁻¹⁵structure-preserving6.5·10⁻⁶the structure is not decorationit is where half the accuracy is

A perturbation that keeps the symmetry

The smallest perturbation that makes a computed answer exact is the backward error. Ask for the smallest one that also keeps the problem's structure and the number can only go up — and measured on a palindromic quadratic it goes up by 1.17, while the structure the computed spectrum has lost is not in either number.

structure · Structured backward error 22.539343.078693.618034.157384.6967210⁻¹110¹10²stiffness damping βoverdamping marginβ* = 3.23607two routes to a boundaryclosed form β*3.2by certificate3.2difference4.7·10⁻¹³bisection steps44a factorisation that completesand a sine, agreeing to twelve digits

A class a longer chain takes away

Symmetry survives a bigger problem. Hyperbolicity does not. The damping that certifies a chain of seven masses is refused by a chain of eight, the damping the class demands grows like the length without bound, and the certificate has to be earned again at every size — which costs one Cholesky, and the alternative is a proof quietly inherited from a smaller problem.

polynomial · Hyperbolic quadratic 11.31.610⁻¹110¹10²10³log₁₀ ntropical root ÷ actual modulusexactsmallest moduluslargest modulusthree norms, two endslarge root, n = 40.96large root, n = 320.94small root, n = 45.4small root, n = 32230a maximum predicts a maximumand says nothing about a minimum

An estimate that does not move

The tropical roots are said to miss the bottom of a spectrum by a factor growing like n². The estimate does not get worse. It changes by four per cent between four masses and sixty-four while the modulus it names falls by a factor of a hundred and sixty, and an estimate that is constant in the variable the answer depends on is a different defect from an inaccurate one.

polynomial · Polynomial scaling finite eigenvalues (degree of det Q)13at infinity (2n − degree)1at infinity, by the rank of M12n, if M were nonsingular14a degree, not a decisiondegree of det Q13at infinity1by the rank of M1singular-value gap∞the count is a degreeand the other route is a judgement

One mass removed, and one eigenvalue gone

A coordinate with no inertia reads like a coordinate that has been deleted, and a chain of eight masses with one of them removed would then be a chain of seven, with fourteen eigenvalues. It has fifteen. The massless coordinate is still there, still carrying a damper, and it contributes a first-order equation rather than none.

polynomial · Polynomial eigenvalue 02468101201change of units, by exponent10⁰10¹10²10³10⁴10⁶10¹⁰10¹⁶10¹⁹10²⁰10⁴⁰10¹⁵⁰as writtenafter scalinga range questionlargest finite value3.4·10³⁸predicted boundary γ1.8·10¹⁹last γ that forms10¹⁹stops where scaling fails0not a poor answerno answer at all

The units that overflow before the answer does

A change of variable that is exact in the algebra requires γ² times a matrix to be a number the format can hold. In binary64 that is a bound nobody meets by accident. In binary32 it arrives at 10¹⁹ and in fp16 at 256, and past it there is no answer rather than a poor one.

arithmetic · Overflow 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 small group, worst backward errorleading, at 4·10¹¹2.7·10⁻⁷flv, at 4·10¹¹7.1·10⁻⁷tropical, at 4·10¹¹10⁻⁵trailing, at 4·10¹¹7.1·10⁻¹⁶both, at 4·10¹¹7.1·10⁻¹⁶10¹10⁵10⁹10¹³10¹⁷10²¹10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²separation ‖C‖²/(‖M‖‖K‖)backward errorleading reductionleading, FLV scalingleading, tropical scalingstrailing reductionboth reductionsdotted grey: u times the separationonly the trailing reduction keeps the small group

Two groups need two reductions

When a quadratic eigenproblem's tropical roots are far apart its eigenvalues fall into two groups, and the remedy offered is a second scaling — one per tropical root, each run keeping the group its root predicts. Raise the damping on an eight-mass chain until the roots are 10²³ apart and measure every eigenvalue: no scaling rescues the small group. Its backward error grows as the unit roundoff times the separation under Fan–Lin–Van Dooren's scaling, under both tropical scalings and under none, to 10⁻⁵ at a separation of 4·10¹¹. What rescues it is the other reduction of the same pencil — inverting the constant term instead of the leading one — which keeps the small group at rounding at every separation and loses the large one instead. Both reductions, each keeping its own group, give all sixteen eigenvalues to 10⁻¹¹ at worst. On the way, the closed form that served as the exact answer turned out to lose the small roots to cancellation, from the same separation.

polynomial · Polynomial scaling 8 massescompanion, ε = 10⁻¹²2.7·10⁻⁹definite, ε = 10⁻¹²0.00210⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²ε, the margin above critical dampingworst relative error of the spectrumcompaniondefinite pencilthe margin shrinks to the leftthe guarantee costs the digits

A guarantee paid for in digits

A hyperbolic quadratic has a real spectrum, but the route that computed it so far, a companion linearisation and a nonsymmetric Schur form, only happens to return one. The theory offers a route on which it cannot do otherwise: a symmetric linearisation that is a definite pencil, reduced by a Cholesky to a symmetric eigenproblem. Near the class's boundary that guarantee is the expensive route. On a damped chain at damping β*(1 + ε) the definite pencil's Crawford number — what its Cholesky divides by — vanishes like 0.228ε, every combination of the pencil shrinking with it, while the colliding pair the companion route has to resolve separates like 0.98√ε. At ε = 10⁻¹² the definite route keeps two or three digits and the companion route eight or nine. And on twenty rotated chains the companion route returns no complex pair at any margin from 10⁻⁴ to 10⁻¹², only on the boundary itself.

polynomial · Hyperbolic quadratic 33.310⁻⁴10⁻³10⁻²10⁻¹1log₁₀ numbers storeddistance to the dominant eigenvalueArnoldi, linearisedprojected quadraticper number heldstorage, linearised2080storage, second-order1040Ritz values, linearised26Ritz values, second-order52half the storageand twice the approximations

A Krylov space for a problem that is not linear

A quadratic eigenvalue problem has no matrix to build a Krylov space out of. The recurrence that builds one anyway stores half as many numbers, returns twice as many Ritz values — and stops being a basis at twenty vectors while the answer it gives keeps improving.

iterative · Krylov 22.32.62.910⁻⁴10⁻³10⁻²10⁻¹1log₁₀ numbers storeddistance to the dominant eigenvalueArnoldi, linearisedprojected quadraticper number heldstorage, linearised832storage, second-order416Ritz values, linearised26Ritz values, second-order52half the storageand twice the approximations

The answer that arrives when the space runs out

A second-order Krylov recurrence holds vectors of length n for a problem with 2n eigenvalues, so it is exact at n steps where the linearised route needs 2n. The machine-precision reading at forty-four vectors on a chain of forty is that exhaustion rather than convergence, and it arrives through a basis whose ‖QᵀQ − I‖ is above one.

iterative · Krylov

Named alongside it

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

Exact ground truthLinearisationMatrix polynomialCondition numberScalingBackward errorCholeskyCompanion formDouble rootHyperbolic quadraticTropical rootsA-priori bound

All concepts