Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Power method — where it appears

Repeated application of a matrix to a vector, which converges to the direction of its largest eigenvalue. It is why a sequence of powers stops being an independent set, at a rate given by the ratio of the two largest eigenvalues.

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 2345678110²10⁴10⁶10⁸10¹⁰vectors in the basisκ₂ of the basisas derivedsolves spread outone subspace, two spanning setseight moments at one point7.7·10⁹eight points, spread1growth per vector661/u4.5·10¹⁵the same subspaceand only one of them usable

A basis that is the same subspace and not the same thing

The interpolation conditions are conditions on a subspace, so any basis of it will do. The one a derivation writes down reaches a condition number of 7.7·10⁹ by its eighth vector, and the rate at which it gets there is set by a number the user chose with no information.

reduction · moment matching

Named alongside it

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

BasisCondition numberConvergence orderDeflationJacobi's eigenvalue methodKrylov subspaceMoment matchingOrthogonalityPerturbationPetrov–GalerkinThe QR algorithmRational krylov

All concepts