Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Pseudospectrum — where it appears

The set of points a perturbation of stated size can move an eigenvalue to, which for a normal matrix is a union of discs and for others is not. It is computed from the norm of the resolvent on a grid, which costs a decomposition per point, and it describes the behaviour a spectrum alone cannot.

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

darker is smaller: 10⁻¹⁰, 10⁻⁶, 10⁻³, 10⁻¹one spectrum, two matricesspectral radius0.8reach of the 10⁻³ level1.3eigenvalues, all at0.8the circle is |z| = 1and every eigenvalue is well inside it

The eigenvalues that are not there

For a normal matrix the resolvent norm is exactly one over the distance to the nearest eigenvalue, so a picture of it carries nothing the spectrum did not. Move one entry above the diagonal and the region a perturbation of 10⁻⁸ can put an eigenvalue into stops being a disc and reaches out past the unit circle, while every eigenvalue stays at 0.8.

spectra · Non-normality 027548110813510⁻⁶10⁻⁴10⁻²110²10⁴10⁶power‖Aᵏ‖Kreiss constant 6760e · n · K‖Aᵏ‖ρᵏtwo routes to one peakspectral radius0.8peak of ‖Aᵏ‖2·10⁴Kreiss constant6757e · n · K1.1·10⁵everything here decays in the endand one of these curves says how much first

A spectral radius that grows first

ρ(A) below one guarantees that the powers of A go to zero and says nothing about what they do on the way. Here they rise by a factor of twenty thousand before turning over, and the peak is bracketed above and below by a constant computed from the resolvent norms outside the unit circle — two routes to one number, one through the plane and one through the powers.

spectra · Non-normality largest eigenvalue erroras given, order 960.043balanced, order 964.4·10⁻⁴symmetrised, order 962.2·10⁻¹²016324864809611210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹order nlargest |computed − exact| eigenvaluean error of one: the integers are no longer told apartas givenbalancedsymmetrisedopen dots: complex pairs returned for a real spectrumevery entry is an integer, stored exactly

Balanced is not symmetric

The Sylvester–Kac matrix is made of small integers, so a double holds it exactly, and its eigenvalues are the integers from −(n − 1) to n − 1 in steps of two. Every digit an eigensolver loses on it is therefore the solver's own, and it loses them at exactly the rate first-order perturbation theory predicts: the median error is half the prediction across 1,568 eigenvalues. Balancing, the preprocessing libraries apply for this kind of matrix, divides every condition number by about sixty and leaves their growth untouched, and at order 112 the unbalanced solver returns eighteen complex eigenvalues for a spectrum of integers.

error · Exact ground truth

Named alongside it

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

Non-normalityEigenvalue condition numberResolventTransient growthAsymptotic analysisConvergence rateExact ground truthFrancis's double shiftThe Kreiss constantNon-normal matricesPerturbationPerturbation theory

All concepts