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. It minimises what it can measure at every step, so its residual falls monotonically, and its rate on a non-normal matrix is not predicted by the eigenvalues.

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

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 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 -1-0.500.511.50eigenvalue of P⁻¹Ktriangular [[H, Aᵀ], [0, −Ŝ]] — 1 valuediagonal blkdiag(H, Ŝ) — 3 valuessteps to a residual of 10⁻¹⁰GMRES, triangular2MINRES, diagonal3‖P⁻¹K − I‖54computed |λ − 1| at c = 18.1·10⁻⁸one copy of each value against twoand the counts follow

One eigenvalue and two steps

Put the off-diagonal block back into a block-diagonal saddle-point preconditioner and every eigenvalue of the preconditioned matrix becomes exactly one. GMRES still needs two steps, because the matrix is the identity plus a nilpotent part of norm 54, and a computed eigenvalue at one comes back as a ring of radius 8·10⁻⁸ — the square root of the rounding, not the rounding. With an approximate Schur complement the triangular form leaves one copy of each value where the diagonal form leaves two, and the step count halves.

constraint · Block preconditioning 024681012141618024681012141618distinct eigenvalues in the spectrumstep the recurrence stops atthe step is m, not nn = 30 throughoutspectra drawn8every one breaking at m8worst residual at the breakdown5.6·10⁻¹⁶smallest gain over the step before3.5·10¹⁰an invariant subspace contains the answerand its dimension is what the method costs

The zero that means it is finished

Every Krylov method ends by dividing by a number the previous step produced, and when that number is zero the recurrence stops. In Arnoldi the stop is the answer — the subspace has closed, the solution is inside it, and the residual is at the unit roundoff. The literature calls it a lucky breakdown, and the adjective is doing real work.

iterative · Breakdown 051015202530354010⁻³10⁻¹10¹GMRES steprelative residualthe two curves are the same curvea number re-derived, not carriedworst reported/actual factor1.8at step40‖VᵀV − I‖ of the basis1.4reported at the last step0.041actual at the last step0.074the same family of methodsand only one of them lies

The number that is re-derived

GMRES prints a residual it never computes from its answer either. On the matrix that sends a conjugate gradient recurrence 7.3·10¹⁰ wrong, and on two others chosen to be worse, its number is never more than a factor of 2.86 out — while the basis it is computed from has lost orthogonality entirely. The disease is not iterative methods, and it is not floating point.

iterative · Residual gap

Named alongside it

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

Krylov subspaceArnoldiArnoldi iterationNon-normalityOrthogonalityResidualBackward errorBlock preconditionerClustered spectrumCondition numberConvergence rateDefective matrix

All concepts