Analysis and Implementation of an Implicitly Restarted Arnoldi Iteration
RICE UNIV HOUSTON TX DEPT OF COMPUTATIONAL AND APPLIED MATHEMATICS
Pagination or Media Count:
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 Sorensens 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 pi 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 manlier. 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 ArnoldiLanczos 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 ArnoldiLanczos 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.
- Theoretical Mathematics
- Operations Research