Analysis and implementation of an implicitly restarted Arnoldi iteration

Abstract

The Arnoldi algorithm, or iteration, is a computationally attractive technique for computing a few eigenvalues and associated invariant subspace of large, often sparse, matrices. The method is a generalization of the Lanczos process and reduces to that when the underlying matrix is symmetric. This thesis presents an analysis of Sorensen's Implicitly Re-started Arnoldi iteration, (scIRA-iteration), by exploiting its relationship with the scQR algorithm. The goal of this thesis is to present numerical techniques that attempt to make the scIRA-iteration as robust as the implicitly shifted scQR algorithm. The benefit is that the Arnoldi iteration only requires the computation of matrix vector products w = Av at each step. It does to rely on the dense matrix similarity transformations required by the EISPACK and LAPACK software packages. Five topics form the contribution of this dissertation. The first topic analyzes re-starting the Arnoldi iteration in an implicit or explicit manner. The second topic is the numerical stability of an scIRA-iteration. The forward instability of the scQR algorithm and the various schemes used to re-order the Schur form of a matrix are fundamental to this analysis. A sensitivity analysis of the Hessenberg decomposition is presented. The practical issues associated with maintaining numerical orthogonality among the Arnoldi/Lanczos basis vectors is the third topic. The fourth topic is deflation techniques for an scIRA-iteration. The deflation strategies introduced make it possible to compute multiple or clustered eigenvalues with a single vector re-start method. The block Arnoldi/Lanczos methods commonly used are not required. The final topic is the convergence typical of an scIRA-iteration. Both formal theory and heuristics are provided for making choices that will lead to improved convergence of an scIRA-iteration.