Every essay — page 8
Eigenvalues, singular values, rank
A symmetric matrix gives up its eigenvalues without complaint. An unsymmetric one can move them by the eighth root of a perturbation, so rounding error alone shifts them by a hundredth. And rank is not a property a floating-point matrix has — it is a decision about a gap, and the gap is worth printing beside it. The algorithm that libraries actually run lives here too, and it needs a shift before it is an algorithm at all.
The largest gap is inside the null space
The rule recommended for counting a pencil's infinite eigenvalues is to cut at the largest gap in the singular values of B. On integer pencils, with no perturbation anywhere and an exact answer available from the characteristic polynomial, it returns the wrong count on nine of twenty-five — because the singular values that are mathematically zero come back spread over a hundred and forty orders of magnitude, and the largest ratio in the list is between two of them.
The same budget, spent five ways
A restarted method has one budget — products with A — and two ways to spend it, in many short cycles or a few long ones. At about a hundred and forty products the answer is the same to a factor of seven whichever split is chosen, and the residual bound the method reports spans ten orders of magnitude across the same five runs.
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.
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.
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.
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.
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.
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.
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.
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.
The problem the solver was actually given
A linearisation is exact — it has the polynomial's eigenvalues, with their multiplicities, and the whole loss is arithmetic. A nonlinear eigenvalue problem does not offer that. Every algorithm replaces the function first, and the term that replacement contributes is committed before any number is rounded and appears in no residual.
An error committed before the arithmetic
Before a nonlinear eigenvalue problem is solved, somebody says where they think the eigenvalues are. That sentence sets the accuracy of everything that follows by five orders, costs nothing to say, and cannot be revised once the approximation built on it is in hand.
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.
The eigenvalues that are answers to nothing
A rational approximant of degree five turns a six-by-six problem into a thirty-six-by-thirty-six one, and thirty-six numbers come back. Six are the answer. The rest are exact eigenvalues of the approximant, lying where the function it approximates is not a real number at all.
A ceiling with a knob on it
A contour method returns at most as many eigenvalues as its probe block has columns, and the object that comes back does not distinguish that from having found everything. One line of the derivation multiplies the ceiling by a number the caller chooses, and it costs no extra solves at all.
The conditioning that rises with the ceiling
Higher moments multiply a contour method's ceiling by K and grade its block Hankel over ρ to the 2K, so the two knobs are the same knob. One division per quadrature point separates them, and the measurement of what it is worth grows from twenty to twenty thousand.
The points the algorithm chose
A rational approximant whose support points are picked by its own residual clusters geometrically at a branch point nobody named — recovering by measurement the rule a hand-built approximant is given. At degree ten it is seven hundred and fifty times more accurate than the same form with its points spread evenly.
A perturbation that moves every coefficient
The backward error of a polynomial eigenpair is measured against perturbations of all three coefficients at once. Restrict it to the one coefficient anybody is willing to move and the same computed answers are stable at one eigenvalue and unstable at another, by a factor that runs from 1.06 to 6,370 across a single spectrum.
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.
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.
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.
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.
Where a contour's budget should go
A contour method's ceiling is the number of probes times the number of moments, and the moments are free in solves while the probes are not. Four ways of reaching one ceiling come out four orders apart, the ordering is not monotone, and what separates the best two is not the usual draw but the unlucky one.
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.
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.