Non-normality — where it appears
Named by 19 essays across 5 fields — each of them below, with the objects they name alongside it.
Symmetry is worth more than precision
A symmetric matrix gives up its eigenvalues to full accuracy however ill-conditioned it is. An unsymmetric one can move them by the eighth root of a perturbation, so the rounding involved in merely storing the matrix shifts the spectrum by a hundredth.
The spectrum that predicts nothing
For a symmetric matrix the eigenvalues govern how fast an iteration converges. Drop symmetry and they stop governing anything — there is a matrix whose eigenvalues are as evenly spread as eigenvalues can be, on which GMRES makes no progress at all until the last possible step.
An equation whose unknown is a matrix
AX + XB = C is linear in X, so it has a coefficient matrix, and writing it down is the obvious thing to do. At n = 100 that matrix has a hundred million entries for a problem with ten thousand unknowns, and the algorithm everybody uses instead never forms it. Its conditioning is not the eigenvalue gap either, which is the number a reader is invited to consult.
A condition number for one eigenvalue
In the symmetric case every eigenvalue has condition number exactly one. In this four-by-four matrix two of them have condition number 100.005 and the other two have exactly 1, and the number belongs to the eigenvalue rather than to the matrix.
A model that cannot be run
A stable system, reduced by matching its transfer function at three points exactly, comes back with a pole in the right half plane at four of nineteen placements — and matches at all three points to 1.3·10⁻¹⁴ while doing it. The construction did what it promised.
Half the conditions and a certificate
A two-sided interpolatory reduction of a stable convection–diffusion system came back unstable at four placements of nineteen. The one-sided reduction built from the same kind of solves came back stable at all 152 placements measured across eight Péclet numbers, and not by luck: every pole of a Galerkin model lies inside the numerical range of the operator, whose edge here is exactly the diffusion term's largest eigenvalue, −0.986 at Péclet 10. The price is the slope conditions, and spent as six one-sided shifts instead of three two-sided ones it beats the stable two-sided model at seven placements of ten.
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.
A certificate written in coordinates
Every one-sided reduced model of the convection–diffusion system was stable, because its poles cannot leave the numerical range and the range sat in the left half plane. Rescale the state by a diagonal matrix and nothing about the system changes — not its eigenvalues, not its transfer function, not one pole of any two-sided model — but the numerical range moves. At Péclet 40 a rescaling with condition number 260 pushes its edge to +6.6 and ten placements of nineteen return unstable one-sided models. Projecting in the inner product of a Lyapunov solution puts the certificate back in any coordinates.
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.
The inner product the mesh already computed
A Galerkin reduced model is certified stable when the operator's numerical range sits in the left half plane, and the certificate belongs to the coordinates. The coordinates that broke it before were a constructed rescaling. Grade a convection–diffusion mesh towards its outflow boundary layer — the grading anyone resolving the layer would choose — and nodal values break it too: the range's edge is past zero at a ratio of ten and reaches +8.9 at a thousand, and at Péclet 100 seven reduced models come back unstable. Weight the projection by the cell sizes the discretisation already computed and every model at every grading is stable, with the range's edge back at −0.098.
A function of a matrix is not a function of its entries
Everybody learns that f(A) means diagonalise, apply f to the eigenvalues, undiagonalise. That is a definition, not a method. On a matrix seven picometres from a defective one — with exact eigenvalues and eigenvectors from a closed form — the definition returns an answer wrong by sixty-five orders of magnitude, and a method that never mentions an eigenvalue returns the right one.
The smaller cell downstream
Nodal values on a convection–diffusion mesh graded towards its outflow layer put the numerical range in the right half plane, and Galerkin reduced models then fail. A code that grades towards the layer usually also upwinds, and upwinding adds diffusion. It does not give the certificate back: at Péclet 100 and a grading of a thousand the range's edge falls from 8.94 to 6.78 and stays positive, and 18 reduced models fail where 23 did. Each row of the upwind stencil's symmetric part sums to half the difference between the inverse widths of the cell after the node and the cell before it, so wherever the cells shrink downstream the dissipation upwinding adds is outweighed by the coupling to the smaller cell next door.
The series that has to be squared back
The Taylor series for the matrix exponential is not wrong — every term is computed correctly — and on Moler and Van Loan's two-by-two its largest term is 5.4 million times the answer it sums to. The method that replaces it scales the matrix down and squares the result back, and both halves of that sentence cost: too few squarings and the approximant is out of range, too many and each one doubles the rounding.
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.
The edge sits where the cells meet the flow
On a convection–diffusion mesh graded towards its outflow, the nodal numerical range reaches into the right half plane, and Galerkin reduced models fail. The account was that the edge lives in the cells where diffusion and convection are comparable, and drawing the eigenvector that attains it says the account is right: on every operator whose mesh has a cell Péclet number above one, the eigenvector peaks where that number is between a half and one and a quarter, just downstream of where it crosses one, and the outflow layer's five smallest cells hold under four per cent of it. The other question has a short answer too. A one-sided stencil scaled by a cell width is dissipative in nodal coordinates only if its weights do not grow downstream, and a consistent one must grow there: the only dissipative weight is the constant one, which is wrong by up to four units of the derivative.
The middle eigenvectors come back exact
The Sylvester–Kac matrix's eigenvectors are known exactly, and the middle ones were predicted to be lost before their eigenvalues, since the gap between neighbouring eigenvalues is only two. Started from the all-ones vector, inverse iteration seems to confirm it: half the middle eigenvectors are wholly wrong at order 80 while their eigenvalues keep five digits. But the all-ones vector has, in exact arithmetic, no component at all along every other eigenvector. From a random start the middle eigenvectors come back exact to fourteen digits at every order measured, while their eigenvalues lose up to eleven. What is lost is at the ends of the spectrum, in the smallest entries of eigenvectors whose entries span twenty decades — and never by more than three units of roundoff times that span.
A weight is not a location
On a mesh graded towards a convection–diffusion operator's outflow, the edge of the numerical range in nodal coordinates lives in the cells where diffusion and convection are comparable, and weighting the inner product by cell size everywhere moves it into the left half plane. The prediction was that the weight is only needed where the edge lives: cell sizes over the nodes whose cell Péclet number is between a quarter and two, and one elsewhere, would make the range dissipative at every grading and repair every failed model. It does the opposite. From a grading of ten the band-only weight's edge is positive, and from thirty it is further right than the nodal edge it was meant to repair — 144 against 8.9 at Péclet 100. Its edge eigenvector leaves the transition and sits at the weight's own step, where it rises from 0.16 to 1; and its models fail on thirteen placements to the nodal twenty-three. The cell sizes work because they are the one diagonal weight that makes the centred convection stencil skew, row by row, and any other — stepped, ramped over half the mesh, or the reverse — leaves a symmetric part where it departs.
The vector moves with its eigenvalue
The Sylvester–Kac matrix's middle eigenvectors came back exact to fourteen digits by inverse iteration while their eigenvalues lost eleven, and the route LAPACK uses — back substitution in the computed Schur form, then the accumulated orthogonal transformation — was predicted to lose them, at about the eigenvalue's error divided by the gap of two: 10⁻⁵ at order 80. It does, at 2.3·10⁻⁵, so the route is the whole of the difference: nine orders of magnitude between two ways of computing the same vectors from the same eigenvalues. The constant is not one over the gap. On all 274 eigenvectors whose eigenvalues are off by more than 10⁻¹¹, at every order from 40 to 80, the Schur route's error is 0.76 to 0.84 times its eigenvalue's error, and 0.79 is a number the exact vectors carry: how fast a unit Krawtchouk vector turns as its eigenvalue moves. The Schur route returns the right eigenvector of a wrong eigenvalue.
The number that is re-derived
GMRES prints a residual it never computes from its answer either. On the matrix that sends a conjugate gradient recurrence 7.3·10¹⁰ wrong, and on two others chosen to be worse, its number is never more than a factor of 2.86 out — while the basis it is computed from has lost orthogonality entirely. The disease is not iterative methods, and it is not floating point.
Named alongside it
The objects these essays reach for when they reach for this one.
Convection diffusionReduced stabilityGalerkin projectionNumerical rangeEigenvalue condition numberExact ground truthTransfer functionCondition numberMass matrixOrthogonalityPetrov–GalerkinRational krylov