Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Double root — where it appears

An eigenvalue of multiplicity two, where two roots of the same polynomial coincide. The map from a coefficient to such a root has an infinite derivative, so a perturbation of size ε moves the root by the square root of ε and a computation in binary64 returns about eight digits rather than sixteen.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

Also named here as hyperbolic quadratic — the same set of essays touches all of them, so they are one junction rather than several.

-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 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 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 00.10.20.30.40.50.6margin ε above the class's boundaryshare of runs with a complex pair10⁻¹⁶10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²0none predicted to the rightmeasured, 100 runsdashed: predicted fromthe boundary's errorsmargin drawn on a logarithmic axis; the boundary at the far lefta coin, below the arithmetic's noise

Real or complex by the sign of an error

A hyperbolic quadratic has only real eigenvalues, and an unstructured solver that knows nothing of the class returned a complex pair for one only at the boundary. The prediction was that the first complex pair would appear at a margin between 10⁻¹⁶ and 10⁻¹⁴ above the boundary, where the colliding pair's separation shrinks to the solver's own perturbation of it, and never at 10⁻¹³ or above. Both hold. Below 10⁻¹⁵ the solver returns a complex pair on almost exactly half of a hundred rotated chains — the same at the boundary itself — because its error in the pair's squared separation has the same size at every margin and either sign, and that one distribution, read at the boundary, predicts the whole curve. The structured route that guarantees a real answer loses every digit first.

polynomial · Hyperbolic quadratic

Named alongside it

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

Hyperbolic quadraticQuadratic eigenvalue problemCholeskyCondition numberExact ground truthOverdampingDefective matrixInertiaLinearisationBackward errorCompanion formDefinite pencil

All concepts