Arnoldi Iteration - The Arnoldi Iteration

The Arnoldi Iteration

The process described above is intuitive. Unfortunately, it is also unstable. This is where the Arnoldi iteration enters.

The Arnoldi iteration uses the stabilized Gram–Schmidt process to produce a sequence of orthonormal vectors, q₁, q₂, q₃, …, called the Arnoldi vectors, such that for every n, the vectors q₁, …, q_n span the Krylov subspace . Explicitly, the algorithm is as follows:

• Start with an arbitrary vector q₁ with norm 1.
• Repeat for k = 2, 3, …
  • for j from 1 to k − 1

The j-loop projects out the component of in the directions of . This ensures the orthogonality of all the generated vectors.

The algorithm breaks down when q_k is the zero vector. This happens when the minimal polynomial of A is of degree k. In most applications of the Arnoldi iteration, including the eigenvalue algorithm below and GMRES, the algorithm has converged at this point.

Every step of the k-loop takes one matrix-vector product and approximately 4mk floating point operations.