Fixed-Polynomial Approximate Spectral Transformations for Preconditioning the Eigenvalue Problem

This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/17630Arnoldi's method is often used to compute a few eigenvalues and eigenvectors of large, sparse matrices. When the eigenvalues of interest are not dominant or wellseparated, this method may suffer from slow convergence. Spectral transformations are a common acceleration technique that address this issue by introducing a modified eigenvalue problem that is easier to solve. This modified problem accentuates the eigenvalues of interest, but requires the solution of a linear system, which is computationally expensive for large-scale problems. Furthermore, ensuring the precision of the computed eigenvalues with respect to the original eigenvalue problem requires restrictive accuracy requirements on the solution of each linear system for the modified eigenvalue problem. This thesis shows how this expense can be reduced through a preconditioning scheme that uses a fixed-polynomial operator to approximate the spectral transformation. These operators are computed prior to being used in Arnoldi's method and eliminate the accuracy requirements on the solution of each linear system for the modified eigenvalue problem. Three different constructions for a fixed-polynomial operator are derived from some common iterative methods for non-Hermitian linear iii systems and the numerical behavior of these three operators are compared. There are significant computational benefits in precomputing an approximation to a spectral transformation, which become apparent in the discussion of implementation details as well as in the development of accuracy heuristics. Numerical experiments demonstrate that this preconditioning scheme is a competitive approach for solving largescale eigenvalue problems. The results illustrate the effectiveness of this technique using several practical eigenvalue problems from science and engineering ranging from hundreds to more than a million unknowns