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]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
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: |
| ||||||
| ORCID: |
| ||||||
| 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: |
| ||||||
| 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
