Session III.1 - Numerical Linear Algebra
Wednesday, June 21, 17:30 ~ 18:00
Randomized Contour Integral Methods for Eigenvalue Problems
Agnieszka Miedlar
Virginia Tech, United States of America - This email address is being protected from spambots. You need JavaScript enabled to view it.
Randomized NLA methods have recently gained popularity because of their easy implementation, computational efficiency, and numerical robustness. In this talk, we present the analysis of a randomized version of a well-established FEAST algorithm that enables computing the eigenvalues of the Hermitian matrix pencil $(A, B)$ located in the given real interval $\mathcal{I} \subset [\lambda_{min}, \lambda_{max}]$. First, we establish new structural as well as probabilistic error analysis of the accuracy of approximate eigenpairs and subspaces obtained using the randomized FEAST algorithm, i.e., bounds for the canonical angles between the exact and the approximate eigenspaces, 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 modified algorithm allows to improve the accuracy of orthogonalization when $B$ is ill-conditioned, efficiently apply the rational filter by using MPGMRES-Sh [Bakhos, Kitanidis, Ladenheim, Saibaba and Szyld, 2016] method to accelerate solving shifted linear systems and estimate the eigenvalue counts in a given interval. Finally, we illustrate numerically the effectiveness of presented error bounds and proposed algorithmic modifications.