Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

GMRES — where it appears

Minimising the residual over the Krylov space of A itself, which for a non-normal matrix is a space the singular value decomposition cannot describe.

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

02468101210⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1iteration‖r‖ / ‖b‖Laplaciancyclic shiftno progress at allevery eigenvalue of the shift is on the unit circleand it predicts nothing

The spectrum that predicts nothing

For a symmetric matrix the eigenvalues govern how fast an iteration converges. Drop symmetry and they stop governing anything — there is a matrix whose eigenvalues are as evenly spread as eigenvalues can be, on which GMRES makes no progress at all until the last possible step.

iterative · gmres 036912151821242700.250.50.7511.25index kweight appliedonebidiagonalArnoldiis it a function of σmisfit, even fit1.6·10⁻¹²misfit, general fit0.063‖A − Aᵀ‖/‖A‖0.086one method's weights do not notice the operatorand the other's stop being a function of σ

The basis decides what a filter is

The vocabulary of regularisation is spectral — a method keeps a component or discards it, and the weights are a function of the singular value. Row-normalising a symmetric blur so that it preserves a constant makes it 8.6% asymmetric, and that is enough to move GMRES's weights from 7·10⁻¹⁴ off a function of σ to 4.4·10⁻².

regularisation · gmres

Named alongside it

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

Krylov subspaceArnoldiArnoldi iterationCondition numberEigenvectorsFilter factorsIll posed problemJacobi's eigenvalue methodLsqrNon normal matrixNon-normalityOrthogonality

All concepts