A Caltech Library Service

Randomized block Krylov methods for approximating extreme eigenvalues

Tropp, Joel A. (2022) Randomized block Krylov methods for approximating extreme eigenvalues. Numerische Mathematik, 150 (1). pp. 217-255. ISSN 0029-599X. doi:10.1007/s00211-021-01250-3.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Randomized block Krylov subspace methods form a powerful class of algorithms for computing the extreme eigenvalues of a symmetric matrix or the extreme singular values of a general matrix. The purpose of this paper is to develop new theoretical bounds on the performance of randomized block Krylov subspace methods for these problems. For matrices with polynomial spectral decay, the randomized block Krylov method can obtain an accurate spectral norm estimate using only a constant number of steps (that depends on the decay rate and the accuracy). Furthermore, the analysis reveals that the behavior of the algorithm depends in a delicate way on the block size. Numerical evidence confirms these predictions.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access Paper
Tropp, Joel A.0000-0003-1024-1791
Additional Information:© The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2021. Received 30 April 2018; Revised 27 September 2021; Accepted 02 October 2021; Published 03 December 2021. This paper was produced under a subcontract to ONR Award 00014-16-C-2009. The author thanks Shaunak Bopardikar, Petros Drineas, Ilse Ipsen, Youssef Saad, Fadil Santosa, and Rob Webber for helpful discussions and feedback. Mark Embree provided very detailed, thoughtful comments that greatly improved the quality of the paper.
Funding AgencyGrant Number
Office of Naval Research (ONR)00014-16-C-2009
Issue or Number:1
Classification Code:Mathematics Subject Classification: Primary 65F30; Secondary 68W20, 60B20
Record Number:CaltechAUTHORS:20220107-890431800
Persistent URL:
Official Citation:Tropp, J.A. Randomized block Krylov methods for approximating extreme eigenvalues. Numer. Math. 150, 217–255 (2022).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:112786
Deposited By: Tony Diaz
Deposited On:09 Jan 2022 00:34
Last Modified:25 Jul 2022 23:14

Repository Staff Only: item control page