Smith Colloquium

September 27, 2018




Yousef Saad, University of Minnesota


Title: Divide and Conquer Algorithms and Software for Large Hermitian Eigenvalue Problems

Abstract: 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.





Smith Colloquium Spring 2018