Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Finite termination — where it appears

The property of reaching the exact answer in a bounded number of steps, which a Krylov method has in exact arithmetic and can lose entirely. It holds in exact arithmetic and is lost in floating point, which is why conjugate gradients is used as an iteration rather than as a direct method.

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

05101520253010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹iteration‖RᵀR − I‖ and ‖r‖/‖b‖step n‖RᵀR − I‖residual30×30, run for exactly n stepsexact arithmetic would end here

An orthogonalisation nobody calls one

Conjugate gradients are derived as a minimisation and behave as an orthogonalisation, which is why the finite-termination property in every textbook is not a property the method has in floating point.

iterative · Krylov 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 ran to the end3173lucky — a subspace closed295serious, cured by a block of two495serious, cured by a longer block29serious, incurable at any length8counted, not estimatedserious, as a fraction0.13of those, cured at two0.93incurable8matrices tried4000measure zero on the realsand an eighth of the integers

The same zero, and nothing was found

Change the recurrence by two lines and the divisor stops being a norm. It becomes an inner product of two vectors from two different sequences, and an inner product of two different vectors is zero on a whole hyperplane — with neither vector anywhere near zero, nothing invariant, and nothing converged. The arithmetic event is identical and the meaning is opposite.

iterative · Breakdown 22.32.62.910⁻⁴10⁻³10⁻²10⁻¹1log₁₀ numbers storeddistance to the dominant eigenvalueArnoldi, linearisedprojected quadraticper number heldstorage, linearised832storage, second-order416Ritz values, linearised26Ritz values, second-order52half the storageand twice the approximations

The answer that arrives when the space runs out

A second-order Krylov recurrence holds vectors of length n for a problem with 2n eigenvalues, so it is exact at n steps where the linearised route needs 2n. The machine-precision reading at forty-four vectors on a chain of forty is that exhaustion rather than convergence, and it arrives through a basis whose ‖QᵀQ − I‖ is above one.

iterative · Krylov

Named alongside it

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

Krylov subspaceLoss of orthogonalityResidualArnoldiInvariant subspaceOrthogonalityBiorthogonalityClustered spectrumCondition numberConjugate gradientsConvergence rateCounterexample

All concepts