The Implicitly Restarted Arnoldi Method

 

This chapter presents an overview of the theory of Krylov subspace projection and the underlying algorithms implemented in ARPACK. The basic Implicitly Restarted Arnoldi Method (IRAM)  is quite simple in structure and is very closely related to the Implicitly Shifted QR-Algorithm for dense problems. This discussion is intended to give a broad overview of the theory and to develop a high level description of the algorithms. Specific implementation details concerned with efficiency and numerical stability are treated in Chapter 5.

  

Figure 4.1: The Implicitly Restarted Arnoldi Method in ARPACK.

• Start: Build a length $m$ Arnoldi factorization ${\bf A} {\bf V}_m = {\bf V}_m {\bf H}_m + {\bf f}_m {\bf e}^T_m$ with the starting vector ${\bf v}_1.$
• Iteration: Until convergence
  1. Compute the eigenvalues $\{ \lambda_j : j = 1,2,\ldots,m\}$ of $\bH_m$. Sort these eigenvalues according to the user selection criterion into a wanted set $\{ \lambda_j : j = 1,2,\ldots,k\}$ and an unwanted set $\{ \lambda_j : j = k+1,k+2,\ldots,m \}.$
  2. Perform $m-k=p$ steps of the QR iteration with the unwanted eigenvalues $\{ \lambda_j : j = k+1, k+2,\ldots,m \}$ as shifts to obtain ${\bf H}_m {\bf Q}_m = {\bf Q}_m {\bf H}_m^+.$
  3. Restart: Postmultiply the length $m$ Arnoldi factorization with the matrix ${\bf Q}_k$ consisting of the leading $k$ columns of ${\bf Q}_m$ to obtain the length $k$ Arnoldi factorization ${\bf A} {\bf V}_m {\bf Q}_k = {\bf V}_m {\bf Q}_k {\bf H}_k^{+} + {\bf f}_k^{+} {\bf e}_k^T,$ where ${\bf H}_k^{+}$ is the leading principal submatrix of order $k$ for ${\bf H}_m^+.$ Set ${\bf V}_k \leftarrow {\bf V}_m {\bf Q}_k.$
  4. Extend the length $k$ Arnoldi factorization to a length $m$ factorization.

The remainder of this chapter will develop enough background to understand the origins, motivation, and expected behavior of this algorithm. The discussion begins with a very brief review of the structure of the algebraic eigenvalue problem and some basic numerical methods that either influence or play a direct role in the IRAM. Overcoming the basic disadvantages of the simple power method motivates the introduction of Krylov subspaces along with the important projection idea and the related approximation properties. The Lanczos/Arnoldi factorization is introduced as a concrete way to construct an orthogonal basis for a Krylov subspace and provides a means to implement the projection numerically. Implicit restarting is introduced as an efficient way to overcome the often intractable storage and computational requirements in the original Lanczos/Arnoldi method. This new technique turns out to be a truncated form of the implicitly shifted QR algorithm and hence implementation issues and ultimate behavior are closely tied to that well understood method. Because of its reduced storage and computational requirements, the technique is suitable for large scale eigenvalue problems. Implicit restarting provides a means to approximate a few eigenvalues with user specified properties in space proportional to where k is the number of eigenvalues sought.

Generalized eigenvalue problems are discussed in some detail. They arise naturally in PDE applications and they have a number of subtleties with respect to numerically stable implementation of spectral transformations. Spectral transformations are presented within the context of the generalized problem as a means to improve the performance of Krylov methods.

The basic iteration of the IRAM is outlined in Figure 4.1 for those familiar with Krylov subspace methods and basic dense eigenvalue methods. In the iteration shown, is an upper Hessenberg matrix, , and the residual vector is orthogonal to the columns of .