AF: Medium: Collaborative research: Advanced algorithms and high-performance software for large scale eigenvalue problems

Scientists and engineers in areas ranging from physics, chemistry, computer science, to economics, and statistics focus considerable attention on computing 'eigenvalues' and 'eigenvectors' of matrices. They are central to the study of vibrations when building earthquake-resistant structures, to energy computation in solid-state physics, and to ranking web search results. In spite of the enormous progress that has been made in the last few decades in solution methods for large eigenvalue problems, the current state-of-the-art methods remains unsatisfactory when dealing with the new generation of problems that need tens of thousands of eigenvectors for matrices that can have sizes in the tens of millions.

In recent years a new class of techniques has emerged that can compute wanted eigenpairs of large matrices by parts. In these methods, 'windows' or 'slices' of the spectrum can be computed independently of one another and orthogonalization between eigenvectors in different slices is no longer necessary. When the number of eigenpairs to be computed is very large this divide-and-conquer approach becomes mandatory because orthogonalizing very large bases is prohibitive. The resulting interior eigenvalue problems arise in a number of other situations and are now considered by the linear algebra community to be among the most challenging numerical problems to solve, and solution methods for handling them are still lagging.

The goal of this project is to advance the state of the art in solution methods for interior eigenvalue problems. The main thrust of the project is the development of novel algorithms based on a combination of Krylov or block-Krylov projection techniques and complex rational filters. A starting point in this investigation is the FEAST approach. This project addresses many interesting questions in several areas, starting with methodologies for solving eigenvalue problems, to approximation theory questions for designing rational filter functions, and ending with effective parallel implementations. Methods based on a domain decomposition framework will also be considered to deal with the common situation where the matrix (or pair of matrices in the generalized case) is (are) distributed.

The broader impacts of this project highlight the impact on training, the dissemination of new efficient software, and the use of the software by-products in specific applications. All general-purpose codes that are developed under this project will be freely distributed into the public domain. This project will have an impact on the training of graduate and undergraduate students in a field that is vital to the needs of academia, industry, and government laboratories.