Iterative Methods for Eigenvalue Computation

The preceding chapter developed QR iteration for computing the full spectrum of a matrix. For very large matrices, however, storing and transforming the whole matrix can be too expensive. Often, an application needs only a few eigenvalues and their eigenvectors. This chapter develops methods designed for that task.

Many large matrices are sparse, meaning that most of their entries are zero. Multiplying such a matrix by a vector can be inexpensive, even when a dense eigenvalue computation is out of reach. The methods in this chapter use these matrix-vector products to build approximations without transforming the full matrix.

The Main Idea

These methods collect directions generated by matrix-vector products into a Krylov subspace. Keeping this space small makes it possible to work with a matrix that would be too large for a full eigenvalue computation.

We represent the action of \(A\) on this subspace by a small matrix. Its eigenvalues and eigenvectors provide approximations for selected eigenpairs of \(A\). The QR methods from the preceding chapter are still useful: they solve this small eigenvalue problem.

The two main methods are Arnoldi iteration for general matrices and Lanczos iteration for symmetric matrices. Both build the subspace progressively, allowing us to improve the approximations as needed.

Chapter Roadmap

The chapter develops these ideas in the following order:

• Projection onto Krylov subspaces explains how to construct the small eigenvalue problem and relate its solutions to the original matrix.

• Arnoldi iteration gives an algorithm for building an orthonormal basis and the associated projected matrix.

• Arnoldi convergence explains how to assess these approximations and why they can improve.

• Lanczos iteration shows how symmetry simplifies Arnoldi and reduces its computational work.

• Lanczos convergence studies the resulting eigenvalue approximations for symmetric matrices.