Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Second order arnoldi — where it appears

A Krylov recurrence for a quadratic eigenvalue problem that stores vectors of the problem's own size rather than of the linearisation's. It builds the same subspace at half the storage, and its basis loses orthogonality where the linearised one does not.

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

11.31.61.92.210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²log₁₀ quadrature pointsdistance from the true counthalf an eigenvaluean integer, eventuallytrue count2at 4 points2at 128 points2finest error1.4·10⁻¹³the integral is an integerand a rounding hides how far it was

The last digit is the cheapest

Every cost curve on this site has the same shape: the first digits are cheap and the last ones are not. One method inverts it. Doubling the work buys twice as many digits as the previous doubling did, so the price of a digit halves every time it is paid.

cost · nonlinear cost 33.310⁻⁴10⁻³10⁻²10⁻¹1log₁₀ numbers storeddistance to the dominant eigenvalueArnoldi, linearisedprojected quadraticper number heldstorage, linearised2080storage, second-order1040Ritz values, linearised26Ritz values, second-order52half the storageand twice the approximations

A Krylov space for a problem that is not linear

A quadratic eigenvalue problem has no matrix to build a Krylov space out of. The recurrence that builds one anyway stores half as many numbers, returns twice as many Ritz values — and stops being a basis at twenty vectors while the answer it gives keeps improving.

iterative · krylov

Named alongside it

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

Krylov subspaceArithmetic costArnoldiContour integralConvergence rateLinearisationModified Gram–SchmidtNonlinear eigenvalue problemOrthogonalityQuadratic eigenvalue problemQuadratureRitz values

All concepts