CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20220909-161413582

[img] PDF - Accepted Version
See Usage Policy.

4MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220909-161413582

Abstract

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
https://arxiv.org/abs/2111.00113arXivDiscussion Paper
ORCID:
AuthorORCID
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
Funders:
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-18-12363
NSFDMS-1952777
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
DOI:10.7907/cmyh-va31
Record Number:CaltechAUTHORS:20220909-161413582
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220909-161413582
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116782
Collection:CaltechACMTR
Deposited By: George Porter
Deposited On:09 Sep 2022 16:30
Last Modified:22 Sep 2022 22:34

Repository Staff Only: item control page