Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Tridiagonal — where it appears

A matrix whose only nonzero entries are on the main diagonal and the two diagonals beside it. Linear systems with one cost a number of operations proportional to the size, and symmetric eigenvalue methods first reduce a dense matrix to this form.

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

-0.16-0.63-0.493.43-0.025-0.632.3-0.69-0.95-1.70.076-0.49-0.694.3-1.6-1.41.93.4-0.95-1.65.40.0141.63-1.7-1.40.0144.60.055-0.0250.0761.91.60.0553.1A, symmetric→-0.164.600004.65.92.500002.51-1.20000-1.24.90.3800000.385.80.2400000.242H = QᵀAQ, tridiagonal‖A − QHQᵀ‖/‖A‖1.1·10⁻¹⁵below the subdiagonal0worst eigenvalue movement7.1·10⁻¹⁵a similarity, so the spectrum is untouched — and every later step is O(n²) rather than O(n³)one reduction, then every iteration is cheapthe eigenvalues did not move

The form that makes it affordable

One Householder reduction, done once, turns every subsequent iteration of the eigenvalue algorithm from cubic to quadratic cost. It changes no answer at all, which is why it is easy to describe as an optimisation and wrong to.

spectra · The QR algorithm 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.

Similarity transformationDeflationEigenvalue condition numberError accumulationExact ground truthFrancis's double shiftHessenberg formHouseholder reflectionJacobi's eigenvalue methodNon-normalityOrthogonalityPerturbation theory

All concepts