Numerical Linear Algebra
where the algebra stops being the arithmetic
Field

The eigenvalue problem that is not linear

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 eigenvalues, and every algorithm anybody runs is an algorithm for something else. What that substitution costs is measurable: the linearisation is solved to the rounding level at every stop of a sweep across which the answer loses eleven orders.
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.

 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.

 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.

 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.

 -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.

 -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.

 -2-101234-5-3-1135real partimaginary part4 insidea countable spectruminside the contour4drawn12existing∞worst branch residual1.6·10⁻¹⁵there is no last eigenvalueso the question has to change

A problem with infinitely many eigenvalues

Let the matrix depend on λ through something that is not a polynomial and three things stop being true at once. There is no linearisation, there is no characteristic polynomial, and "compute the spectrum" is not a request that can be granted — the only finite question is how many eigenvalues are inside this circle.

All essays