Analysis and Implementation of an Implicitly Restarted Arnoldi Iteration
DateMay 1995 (Revised October 1995)
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, (IRA-iteration), by exploiting its relationship with the QR algorithm. The goal of this thesis is to present numerical techniques that attempt to make the IRA-iteration as robust as the implicitly shifted QR algorithm. The benefit is that the Arnoldi iteration only requires the computation of matrix vector products w=Av at each step. It does not 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 IRA-iteration. The forward instability of the QR 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 IRA-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 IRA-iteration. Both formal theory and heuristics are provided for making choices that will lead to improved convergence of an IRA-iteration.
This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/16844
Citable link to this pagehttps://hdl.handle.net/1911/101858
MetadataShow full item record
- CAAM Technical Reports