TSIRM: A Two-Stage Iteration with least-squares Residual Minimization algorithm to solve large sparse linear systems

In this article, a two-stage iterative algorithm is proposed to improve the convergence of Krylov based iterative methods, typically those of GMRES variants. The principle of the proposed approach is to build an external iteration over the Krylov method, and to frequently store its current residual (at each GMRES restart for instance). After a given number of outer iterations, a least-squares minimization step is applied on the matrix composed by the saved residuals, in order to compute a better solution and to make new iterations if required. It is proven that the proposal has the same convergence properties than the inner embedded method itself. Experiments using up to 16,394 cores also show that the proposed algorithm runs around 5 or 7 times faster than GMRES.