Back to Search Start Over

FAST AND ACCURATE RANDOMIZED ALGORITHMS FOR LINEAR SYSTEMS AND EIGENVALUE PROBLEMS.

Authors :
YUJI NAKATSUKASA
TROPP, JOEL A.
Source :
SIAM Journal on Matrix Analysis & Applications. 2024, Vol. 45 Issue 2, p1183-1214. 32p.
Publication Year :
2024

Abstract

This paper develops a class of algorithms for general linear systems and eigenvalue problems. These algorithms apply fast randomized dimension reduction ("sketching") to accelerate standard subspace projection methods, such as GMRES and Rayleigh-Ritz. This modification makes it possible to incorporate nontraditional bases for the approximation subspace that are easier to construct. When the basis is numerically full rank, the new algorithms have accuracy similar to classic methods but run faster and may use less storage. For model problems, numerical experiments show large advantages over the optimized MATLAB routines, including a 70x speedup over gmres and a 10x speedup over eigs. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
08954798
Volume :
45
Issue :
2
Database :
Academic Search Index
Journal :
SIAM Journal on Matrix Analysis & Applications
Publication Type :
Academic Journal
Accession number :
178608699
Full Text :
https://doi.org/10.1137/23M1565413