The numerical solution of large, sparse Hermitian Eigenvalue Problems (HEP) and Generalized HEP (GHEP) for a few extreme eigenvalues is one of the most important but also computationally intensive tasks in a variety of applications. Examples abound in spectral graph partitioning, large scale spectral graph analysis, structural engineering, electromagnetics, lattice Quantum Chromodynamics, and electronic structure applications from atomic scale physics to molecular scale materials science. Closely related is the problem of computing a partial Singular Value Decomposition (SVD) of a matrix, which finds everyday use in numerous applications including data mining and machine learning. The importance of the problem is evidenced by the significant resources that have been invested over the last decade in developing high quality eigenvalue software packages. However, these packages still do not include the near-optimal methods that have made the package PRIMME the software to beat. PRIMME, or PReconditioned Iterative MultiMethod Eigensolver, is a software package developed in 2005 for the solution of HEP. PRIMME brings state-of-the-art preconditioned iterative methods from "bleeding edge" to production, with a flexible, yet highly usable interface. Yet, it is its focus on numerical robustness and computational efficiency that has gained PRIMME the recognition as one of the best eigenvalue packages. This success calls for a new effort to extend PRIMME with some long awaited functionality but also to include new algorithms to address some outstanding problems in eigenvalue computations. This work is critical to many groups whose research depends on the lattice QCD and materials science software packages that PRIMME will improve through collaborations. PRIMME already has a PETSc interface, and with the proposed development of Hypre and Trilinos interfaces, it will be accessible by a far wider community of users. The most requested feature, however, has been a MATLAB interface. This will unleash the power of an "industrial strength" software to end users. Last but not least, this project will educate and train two graduate and several undergraduate students in the art of high performance numerical software.
Specific goals for this projects include: PRIMME extension to GHEP, with special attention to ill conditioned mass matrices; PRIMME extension to SVD, with special attention to obtaining results at high accuracy (the solution must include not only PRIMME's robust components but a combination of known and new methods, as well as a dynamic way to choose between them); implementation of new methods and techniques for the solution of highly interior eigenvalue problems and for the computation of a large number of eigenvalues; interoperability with DOE libraries and MATLAB, and improved means of dissemination. As a numerical linear algebra kernel, PRIMME has a large potential audience in the computational sciences community. However, two specific collaborations will provide real-world, challenging problems and serve as a stress-test evaluator of the resulting methods and software. One involves the lattice QCD group at the DOE's Jefferson Lab, and the other involves the high performance computing and materials science group at IBM, Zurich.
