Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

The QR algorithm — where it appears

Factorise, multiply the factors back in the other order, repeat — the iteration every dense eigenvalue library runs, with a shift and a deflation criterion.

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

0357010514017521024528010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration|subdiagonal entry|no shiftRayleighWilkinsontwo routes to one raterate, from the spectrum0.9rate, measured0.9iterations, none / Wilkinson45symmetric 4×4, spectrum 8, 4, 2, 1.8the dashed line is the prediction

The algorithm the libraries actually run

Factorise, multiply the factors back in the other order, repeat. That description is complete and correct and produces something nobody would use — on a matrix with eigenvalues +1 and −1 it does not converge at all, and the subdiagonal entry does not move by so much as a rounding error.

spectra · qr algorithm 10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²-1-0.500.51relative backward error acceptedfraction of the work not doneQR deflation criterionincomplete Cholesky droplow-rank truncationthree fields, no shared arithmeticslope, deflation criterion0.039slope, drop tolerance0.051slope, rank truncation0.23widest apart, as a ratio5.7a tolerance is an offerand the three offers are one offer

The zero you are allowed to write

A deflation criterion sets a subdiagonal entry to zero because it is small. A drop tolerance discards an entry of a factor because it is small. A truncation discards a singular value because it is small. Three fields, three vocabularies, no shared arithmetic — and plotted as work saved against error accepted, one curve.

error · deliberate zero

Named alongside it

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

DeflationBackward errorConvergence orderDrop toleranceEckart–YoungIncomplete factorisationJacobi's eigenvalue methodLow-rank approximationPerturbationPreconditioningShiftsSimilarity transformation

All concepts