Subspace Iteration with Approximate Spectral Projection


Ping Tak Peter Tang
2014-05-16  14:20 - 15:30
Room 440, Astronomy and Mathematics Building

The calculation of a segment of eigenvalues and their corresponding eigenvectors of a Hermitian matrix or matrix pencil has many applications. A new approach to this calculation based on a density matrix has been proposed recently [1] and a soft- ware package FEAST [3] has been developed. The density-matrix approach allows FEAST’s implementation to exploit a key strength of modern computer architectures, namely, multiple levels of parallelism. Consequently, the software package has been well received. Nevertheless, theoretical analysis of FEAST has been lagging and that a convergence proof has yet to be established until very recently [2]. In this talk, we introduce offer a numerical analysis of FEAST. In particular, we show that the FEAST algorithm can be understood as the standard subspace iteration algorithm in conjunc- tion with the Rayleigh-Ritz procedure. The novelty of FEAST is that it does not iterate directly with the original matrices, but instead iterates with an approximation to the spectral projector onto the eigenspace in question. Analysis of the numerical nature of this approximate spectral projector and the resulting subspaces generated in the FEAST algorithm not only establishes the algorithm’s convergence, but also provides a number of other properties that can be leveraged to enhance FEAST’s robustness.

References [1] E. Polizzi, “Density-Matrix-Based Algorithm for Solving Eigenvalue Problems”, Physical Review B, vol. 79, num. 115112, 2009
[2] P. T. P. Tang, E. Polizzi, “FEAST as a Subspace Iteration Eigensolver Accelerated by Approximate Spectral Projector”, SIAM Journal on Matrix Analysis and Applications vol. 35, num. 2, pages 354–390, 2014
[3] E. Polizzi, polizzi/feast/, “The FEAST Solver”, 2009