Computing Interior Eigenvalues of Large Matrices by Preconditioned Krylov Subspace Methods

Computing interior eigenvalues of large matrices arises in various important applications such as electromagnetic field simulations in cavities for particle accelerator models and the Anderson model of localization in quantum mechanics. In spite of tremendous progresses made in developing iterative methods and software packages for large-scale eigenvalue problems, these applications pose a significant challenge because, to compute interior eigenvalues, most of the existing methods need to be combined with a shift-and-invert transformation, which may not be practical. The objective of this proposal is to develop preconditioned Krylov subspace methods with analysis for computing a few interior eigenvalues of Ax = )"Bx and to implement them in a black-box software package for public distributions. In a previous work of PI, a method of this type has been developed for computing the smallest or largest eigenvalue of the symmetric problems (A, B symmetric and B > 0), which has also been implemented in a library-quality software called eigifp. Here, it is proposed to develop a generalization for computing interior eigenvalues first for the symmetric problem and then for the nonsymmetric problem. The resulting algorithms should inherit desirable characteristics of the existing Krylov subspace methods, but should allow convergence acceleration through the use of a pre conditioner (or approximate inverse) for A - )"B rather than its inverse. In the course of this project, two possible approaches for the symmetric case will be studied, with the first based on transformations to an extreme eigenvalue problem and the second based on a generalization of the Rayleigh-Ritz method for extracting an interior eigenvector from a subspace. Their feasibility has been demonstrated by some preliminary works and here their convergence properties and preconditioning strategies will be further investigated. Some basic theoretical questions concerning optimally constructing a subspace and extracting approximations from a subspace will be studied. Drawing on earlier works on the nonsymmetric Lanczos algorithm, the second approach will be generalized to the nonsymmetric problem. The resulting algorithms will be implemented in a black-box setting. The proposed works would advance the theory, algorithms and softwares for the interior eigenvalue problem. By developing an efficient software that could be widely used by nonexpert users, this research is expected to generate a strong impact.