Divide and Conquer Algorithms for Large Hermitian Eigenvalue Problems

Yousef Saad
University of Minnesota
Distinguished Professor of Computer Science

“Divide-and-conquer paradigms can lead to efficient and flexible techniques for solving large Hermitian eigenvalue problems. This talk will discuss how these techniques can be put to work to implement `spectrum slicing’ strategies, i.e., strategies that extract slices of the spectrum independently. The presentation will begin with an overview of polynomial filtering, a general approach that can be quite efficient in the situation where the matrix-vector product operation is inexpensive and when a large number of eigenvalues is sought. We will present a few techniques based on the Lanczos algorithm with and without restarts, as well as subspace iteration. An alternative to polynomial filtering that is generating a growing interest is a class of methods that rely on rational functions. Good representatives of this general approach are the FEAST eigensolver and the Sakurai-Sugiura algorithm. We will argue that the standard Cauchy integral–based approach can be substantially improved upon — especially when iterative solvers are involved. Finally, the talk will discuss our recently released code named EVSL (for eigenvalues slicing library) that implements these ideas.”

Light refreshments will be served @ 1:30PM in EMS E424A.