Krylov subspaces and Arnoldi

For a square matrix A and nonzero starting residual r₀, the kth Krylov space is the span of r₀, Ar₀, and successive powers through A to the power k−1 applied to r₀. A correction chosen from this space is a polynomial in A acting on r₀. The space depends on the starting vector as well as the matrix: an eigenvector seed produces only one dimension, even for a large matrix with many eigenvalues. Changing the right-hand side can therefore change the entire convergence history.

Explicitly storing raw powers is usually a poor numerical strategy. Dominant directions can overwhelm weak ones, making successive vectors nearly parallel and difficult to distinguish in finite precision. Arnoldi instead starts with v₁=r₀/‖r₀‖ and orthogonalizes each new matrix image against the existing basis. The intended columns satisfy VᵀV=I. That property is not merely cosmetic; it makes coefficient norms match physical vector norms and supports the small least-squares residual formulas used later.

At step j, compute w=Avⱼ. For each existing basis vector vᵢ, form its inner product with w, store that coefficient, and subtract the corresponding projection. The norm of the final w is hⱼ₊₁,ⱼ; if it is nonzero, divide by it to obtain the next unit vector. The resulting relation has no coefficients below the first subdiagonal because each new image lies in the span of the old basis plus one new direction. An additional orthogonalization pass can reduce numerical loss of orthogonality.

In exact arithmetic, a zero final norm means the current space is invariant under A. No new direction can be generated from that seed. This is often called a happy breakdown when it allows the desired problem to be solved within the invariant subspace, but the interpretation depends on the problem. For a nonsingular linear system with the initial residual as seed, exact residual minimization can then reach the solution. For a singular or inconsistent system, invariant-subspace termination alone need not mean zero residual. A very small floating-point norm also needs a tolerance-aware interpretation rather than division without checking.

Each new Arnoldi step uses one matrix-vector product, but also inner products and updates against every stored basis vector. Storage grows with the number of vectors, and orthogonalization work grows with the basis size. On distributed hardware, global reductions for inner products may cost more than local arithmetic. Restarting limits these costs by discarding or compressing the basis, but can lose valuable polynomial information. A shorter memory footprint can therefore change convergence, not just implementation efficiency.

The small Hessenberg matrix is useful for several different algorithms. GMRES uses the extended Arnoldi relation to minimize a residual norm, while a Ritz eigensolver diagonalizes a projected matrix. These are distinct objectives built on the same basis construction. Verify both orthogonality and the Arnoldi relation when diagnosing an implementation. A plausible projected eigenvalue or a decreasing recursively updated residual can be misleading if the basis has lost orthogonality substantially. Large-scale methods still depend on trustworthy small linear algebra.