Divide and conquer algorithms for large Hermitian eigenvalue problems

Yousef Saad, University of Minnesota
April 22nd, 2015 at 2:30PM–3:30PM in 939 Evans Hall [Map]

Algorithms based on Divide and conquer paradigms can lead to complex, but efficient and flexible algorithms for solving large Hermitian eigenvalue problems. This talk will discuss how various such strategies can be combined to exploit both `spectrum slicing', i.e., computing slices of the spectrum independently, and domain decomposition. These strategies are independent of each other but both are essential if one has to compute very large parts of the spectrum, as is the case in approaches that deal with excited states in solid state physics. The presentation will begin with an overview of polynomial filtering techniques. This general approach 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 present an algorithm (and package) that combines the Lanczos algorithm with partial reorthogonalization and polynomial filtering. An alternative to polynomial filtering that is generating a growing interest is a class of methods that exploit filtering by rational functions. Good representatives of this general approach are the FEAST eigensolver and the Sakurai-Sugiura algorithm. Here we will argue that the standard way of selecting these rational filters, which is based on using the Cauchy integral, can be substantially improved – especially when iterative solvers are involved. Finally, the talk will discuss our ongoing work on Domain-Decomposition (DD) type methods that rely on spectral Schur complements combined with Newton's iteration.