Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Restarting — where it appears

Beginning a Krylov method again from a better starting point rather than letting its basis grow, either by filtering the vector or by keeping the wanted pairs. It bounds the storage at the price of throwing away a subspace, and what a restart keeps — a filtered vector, or the wanted Ritz pairs — is the difference between the standard variants.

Named by 3 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 1234567891010⁻⁵⁵10⁻⁴⁹10⁻⁴³10⁻³⁷10⁻³¹10⁻²⁵10⁻¹⁹10⁻¹³10⁻⁷10⁻¹cyclesizethe residualrepairedthe reported boundwhat the stopping rule readsreported at the last cycle9.4·10⁻⁴¹the residual there5.7·10⁻⁵with the border recomputed3.8·10⁻¹⁴products, cheap and repaired9a bound with nothing under itand one product a cycle to fix it

Keeping the vectors, and losing the bound

Thick restarting keeps the Ritz vectors instead of filtering the starting vector — the same eigenvalues for a third of the products with A. Its residual bound reaches 9.4·10⁻⁴¹ while the residual it bounds sits at 5.7·10⁻⁵, and the eigenvalues are correct to 4.3·10⁻¹⁴ the whole time, so nothing reports it.

spectra · Lanczos 0183654729010812610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹products with Asizeresidual boundtrue errorbounded memorybasis vectors kept8products with A140worst error in the k wanted7.1·10⁻¹⁵the bound is free and the error is notand the basis never grows

The same budget, spent five ways

A restarted method has one budget — products with A — and two ways to spend it, in many short cycles or a few long ones. At about a hundred and forty products the answer is the same to a factor of seven whichever split is chosen, and the residual bound the method reports spans ten orders of magnitude across the same five runs.

spectra · Lanczos

Named alongside it

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

Ritz valuesInvariant subspaceKrylov subspaceLanczos algorithmReorthogonalisationResidual boundStopping criterionArrowhead matrixEigenvalue gapFilter factorsLanczosRayleigh quotient

All concepts