fastGMRES: Robust randomized GMRES via flexible GMRES

Abstract

We propose a practical randomized algorithm for solving large sparse systems of linear equations. The algorithm, termed fastGMRES, uses flexible GMRES as an outer wrapper for sketched GMRES together with a practical residual bound to terminate the inner iteration. We demonstrate that fastGMRES requires very little parameter tuning, while still being efficient and robust in the sense of generating non-increasing residual norms. We observe that the inner sketched GMRES method can be run without any inner product computations and vector--vector updates on high-dimensional vectors, yielding significant speedup for many problems.