Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Breakdown — the series

4 essays on 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.

    part 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.

    part 2 · iterative
  3. 012345678-7-5-3-11357conjugate gradient steppᵀAp ⁄ pᵀpλₘᵢₙ = -0.1positive: a step existsnegative: a certificate existsone matrix, two questionsstep it turns at6quotient there-0.027share of λₘᵢₙ recovered0.27λₘᵢₙ, 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. The guard against it has been here from the first essay 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.

    part 3 · iterative
  4. 10⁻³10⁻²10⁻¹1024681012size of the negative eigenvalue, −λproducts before the test firesharder to find, and milder8 spectra, n = 50products at the largest λ3products at the smallest10smallest share of λ recovered0.14largest0.34the one that hidesis the one that matters least

    A proof that does not ask how large the matrix is

    Proving a Hessian indefinite costs three matrix–vector products when the negative eigenvalue is 3 and nine to eleven when it is a thousandth, and that pair of numbers barely moves across a fourfold range in n. The factorisation that settles the same question costs a third of n³, which grows by a factor of sixty-four over the same range.

    part 4 · iterative

All series