Premium
Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen–Loève expansion
Author(s) -
Saibaba Arvind K.,
Lee Jonghyun,
Kitanidis Peter K.
Publication year - 2016
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2026
Subject(s) - hermitian matrix , mathematics , eigenvalues and eigenvectors , singular value decomposition , singular value , divide and conquer eigenvalue algorithm , algorithm , eigendecomposition of a matrix , randomized algorithm , convergence (economics) , positive definite matrix , a priori and a posteriori , pure mathematics , physics , philosophy , epistemology , quantum mechanics , economics , economic growth
Summary We describe randomized algorithms for computing the dominant eigenmodes of the generalized Hermitian eigenvalue problem A x = λ B x , with A Hermitian and B Hermitian and positive definite. The algorithms we describe only require forming operations A x , B x and B −1 x and avoid forming square roots of B (or operations of the form, B 1/2 x or B −1/2 x ). We provide a convergence analysis and a posteriori error bounds and derive some new results that provide insight into the accuracy of the eigenvalue calculations. The error analysis shows that the randomized algorithm is most accurate when the generalized singular values of B −1 A decay rapidly. A randomized algorithm for the generalized singular value decomposition is also provided. Finally, we demonstrate the performance of our algorithm on computing an approximation to the Karhunen–Loève expansion, which involves a computationally intensive generalized Hermitian eigenvalue problem with rapidly decaying eigenvalues. Copyright © 2015 John Wiley & Sons, Ltd.