Title: Randomized Contour Integral Methods for Eigenvalue Problems with Probabilistic Error Analysis

Abstract: Randomized NLA methods have recently gained popularity because of their easy implementation, computational efficiency, and numerical robustness. We propose a randomized version of a well-established FEAST eigenvalue algorithm that enables computing the eigenvalues of the Hermitian matrix pencil (A, B) located in the given real interval I ⊂ [λmin, λmax].

In this talk, we present the analysis of this randomized variant of the subspace iteration method using a rational filter and propose several modifications of the original FEAST algorithm. First, we derive some new structural as well as probabilistic error analysis of the accuracy of approximate eigenpair and subspaces obtained using the randomized FEAST algorithm, i.e., bounds for the canonical angles between the exact and the approximate eigenspaces corresponding to the eigenvalues contained in the interval, and for the accuracy of the eigenvalues and the corresponding eigenvectors. Since this part of the analysis is independent of the particular distribution of an initial subspace, we denote it as structural. In the case of the starting guess being a Gaussian random matrix, we provide more informative, probabilistic error bounds. Our new algorithm allows to improve the accuracy of orthogonalization when B is ill-conditioned, efficiently apply the rational filter by using MPGMRES-Sh Krylov subspace method to accelerate solving shifted linear systems and estimate the eigenvalue counts in a given interval. Finally, we will illustrate numerically the effectiveness of presented error bounds and proposed algorithmic modifications. This is a joint work with E. de Sturler (VT) and A. K. Saibaba (NC State).