Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

GMRES — the series

2 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · iterative
  2. 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⁻².

    part 2 · regularisation

All series