Numerical Linear Algebra
where the algebra stops being the arithmetic
Ladder

Breakdown — the ladder

3 distinct arguments against one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    rung 1 · iterative
  2. 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.

    rung 2 · iterative
  3. 012345678-7-5-3-11357conjugate gradient steppᵀAp ⁄ pᵀpλ_min = -0.1positive: a step existsnegative: a certificate existsone matrix, two questionsstep it turns at6quotient there-0.027share of λ_min recovered0.27λ_min, by construction-0.1MINRES steps on the same system37the division that cannot be doneis the answer to a different question

    The division that cannot be done

    Conjugate gradients divides by pᵀAp at every step, and on a matrix that is not positive definite that number can be zero or negative. This site has guarded against it since its first commit and described it as a failure. In the method that made conjugate gradients famous it is the single most valuable object the iteration can produce, and it costs six matrix–vector products.

    rung 3 · iterative

All ladders