This research focuses on finding a large number of eigenvalues and
eigenvectors of a sparse symmetric or Hermitian matrix, for example,
finding 1000 eigenpairs of a 100,000 $\times$ 100,000 matrix. These
eigenvalue problems are challenging because the matrix size is too large
for traditional QR based algorithms and the number of desired eigenpairs
is too large for most common sparse eigenvalue algorithms. In this
thesis, we approach this problem in two steps. First, we identify a
sound preconditioned eigenvalue procedure for computing multiple
eigenpairs. Second, we improve the basic algorithm through new
preconditioning schemes and spectrum transformations.
Through careful analysis, we see that both the Arnoldi and Davidson
methods have an appropriate structure for computing a large number of
eigenpairs with preconditioning. We also study three variations of
these two basic algorithms. Without preconditioning, these methods are
mathematically equivalent but they differ in numerical stability and
complexity. However, the Davidson method is much more successful when
preconditioned. Despite its success, the preconditioning scheme in the
Davidson method is seen as flawed because the preconditioner becomes
ill-conditioned near convergence. After comparison with other methods,
we find that the effectiveness of the Davidson method is due to its
preconditioning step being an inexact Newton method. We proceed to
explore other Newton methods for eigenvalue problems to develop
preconditioning schemes without the same flaws. We found that the
simplest and most effective preconditioner is to use the Conjugate
Gradient method to approximately solve equations generated by the Newton
methods. Also, a different strategy of enhancing the performance of the
Davidson method is to alternate between the regular Davidson iteration
and a polynomial method for eigenvalue problems. To use these
polynomials, the user must decide which intervals of the spectrum the
polynomial should suppress. We studied different schemes of selecting
these intervals, and found that these hybrid methods with polynomials
can be effective as well. Overall, the Davidson method with the CG
preconditioner was the most successful method the eigenvalue problems we
tested.