Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Residual bound — where it appears

The number a Krylov method quotes in place of a residual it does not form, read off its projected matrix rather than off its answer. It is the last off-diagonal of that matrix times the last entry of the eigenvector belonging to the Ritz value, so it costs no product with the operator — and it equals the true residual only while the projection still describes that operator.

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

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.

RestartingRitz valuesStopping criterionArrowhead matrixEigenvalue gapInvariant subspaceKrylov subspaceLanczosLanczos algorithmRayleigh quotientReorthogonalisationResidual

All concepts