A Caltech Library Service

Fast & accurate randomized algorithms for linear systems and eigenvalue problems

Nakatasukasa, Yuji and Tropp, Joel A. (2021) Fast & accurate randomized algorithms for linear systems and eigenvalue problems. ACM Technical Reports, 2021-01. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper develops a new class of algorithms for general linear systems and eigenvalue problems. These algorithms apply fast randomized sketching to accelerate subspace projection methods, such as GMRES and Rayleigh--Ritz. This approach offers great flexibility in designing the basis for the approximation subspace, which can improve scalability in many computational environments. The resulting algorithms outperform the classic methods with minimal loss of accuracy. For model problems, numerical experiments show large advantages over MATLAB's optimized routines, including a 100× speedup over gmres and a 10× speedup over eigs.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription Paper
Tropp, Joel A.0000-0003-1024-1791
Alternate Title:Fast and accurate randomized algorithms for linear systems and eigenvalue problems
Additional Information:29 October 2021. Revised: 4 February 2022. JAT acknowledges ONR BRC N00014-1-18-2363 and NSF FRG 1952777. The authors would like to thank Oleg Balabanov, Alice Cortinovis, Ethan Epperly, Laura Grigori, Ilse Ipsen, Daniel Kressner, Gunnar Martinsson, Maike Meier, Florian Schaefer, Daniel Szyld, Alex Townsend, Nick Trefethen, and Rob Webber for valuable discussions and feedback. We are grateful to Zdeněk Strakoš for sharing his insights on Krylov subspace methods and the prospects for sGMRES and sRR.
Group:Applied & Computational Mathematics
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-18-12363
Subject Keywords:Eigenvalue problem, linear system, numerical linear algebra, Petrov–Galerkin method, projection method, randomized algorithm, Rayleigh-Ritz, sketching, subspace embedding
Series Name:ACM Technical Reports
Issue or Number:2021-01
Classification Code:AMS subject classifications. 65F10, 65F15, 65F25
Record Number:CaltechAUTHORS:20220909-161413582
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116782
Deposited By: George Porter
Deposited On:09 Sep 2022 16:30
Last Modified:22 Sep 2022 22:34

Repository Staff Only: item control page