Result: Fast and Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems

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.
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.
Accepted Version - NT21-Fast-Accurate-TR.pdf