Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Three-term recurrence — where it appears

The relation that lets a symmetric Krylov method generate its next basis vector from the previous two, without storing the rest. It is what makes a symmetric Krylov method affordable at any size, and what makes its loss of orthogonality unrecoverable without extra storage.

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

1357910⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1eigenvalue λamplificationkeptdiscardeda filter on the starting vectormeasured against the polynomial3.9·10⁻¹¹worst kept direction1best discarded direction0.8the roots are the discarded Ritz valuesand the vertical lines are where they sit

Restarting is a filter

A restart throws away the Ritz values it does not want and begins again from a new starting vector. Written in the eigenbasis, that vector's components have been multiplied by a polynomial with its roots at the discarded values — measured component by component, and agreeing with the polynomial to rounding.

spectra · Lanczos λ = 105 timesλ = 9.55 timesλ = 95 timesλ = 8.55 timesλ = 2.952 timesλ = 2.92 timeseigenvalues that arrived more than once — the matrix has 40 distinct onesa spectrum with the wrong multiplicitiesextra copies, no reorthogonalisation25extra copies, full reorthogonalisation0worst relative error among the copies1.9·10⁻⁸steps taken of 80 asked for, full40no arithmetic error was madeevery one of these is right to eight digits

An eigenvalue that arrives twice

A matrix with forty distinct eigenvalues, handed to Lanczos for eighty steps, returns twenty-five extra copies of thirteen of them — the largest arriving five times. Every copy is accurate to 1.9·10⁻⁸ relative. No arithmetic error was made, nothing overflowed, and a caller counting eigenvalues gets the wrong multiplicity from a computation in which no individual number is wrong.

spectra · Lanczos

Named alongside it

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

Krylov subspaceLanczos algorithmReorthogonalisationRitz valuesEigenvaluesFilter factorsInvariant subspaceMultiplicityOrthogonalityRestarting

All concepts