UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Spectral slicing for Hermitian matrices based on Zolotarev’s functions

PDE and Applied Math Seminar

Speaker: Yingzhou Li, Stanford University
Related Webpage: http://web.stanford.edu/~ryanlee/
Location: 1147 MSB
Start time: Fri, Apr 21 2017, 4:10PM

This work proposes an efficient method for computing selected generalized eigenpairs of a sparse Hermitian definite matrix pencil (A,B). Based on Zolotarev’s best rational function approximations of the signum function and conformal maps, we construct the best rational function approximation of a rectangular function supported on an arbitrary interval. This new best rational function approximation is applied to construct spectrum filters of (A,B). Combining fast direct solvers and the shift-invariant GMRES, a hybrid fast algorithm is proposed to apply spectral filters efficiently. Assuming that the sparse Hermitian matrices A and B are of size N × N with O(N) nonzero entries, the computational cost for computing O(1) interior eigenpairs is bounded by that of solving a shifted linear system (A − σB)x = b. Utilizing the spectrum slicing idea, the proposed method computes the full eigenvalue decomposition of a sparse Hermitian definite matrix pencil via solving O(N) linear systems. The efficiency and stability of the proposed method are demonstrated by numerical examples of a wide range of sparse matrices. Compared with existing spectrum slicing algorithms based on contour integrals, the proposed method is faster and more reliable.

This is joint work with Haizhao Yang.