TSIRM: A two-stage iteration with least-squares residual minimization algorithm to solve large sparse linear and nonlinear systems

In this paper, 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 as the inner embedded method itself. Several experiments have been performed using the PETSc toolkit (using default parameters in the absence of detail) to solve linear and nonlinear problems. They show good speedups compared to GMRES with up to 16,394 cores with different preconditioners.