A residual replacement strategy for improving the maximum attainable accuracy of \(s\)-step Krylov subspace methods (Q2877077)

Krylov subspace methods (KSMs) are algorithms commonly used for solving systems of linear algebraic equations with large and sparse matrix of the system. These algorithms are based on an iterative improvement in each iteration. In particular, in the \(n\)-th iteration, the solution \(x_n\) and the residual \(r_n\) are updated. In current computer systems, the most limiting factor in the performance of these algorithms is a movement of data. The technique based on an \(s\)-step formulation reduces the data movement by a factor of \(\mathcal{O}(s)\). The authors provide the first quantitative analysis of the maximum attainable accuracy of communication-avoiding Krylov subspace methods in finite precision.NEWLINENEWLINEIn the paper, the ``\(s\)-step KSM'' methods refer to variants of Krylov methods, where the iteration loop is split into an outer loop and an inner loop. The inner loop computes \(s\) steps of the iteration process for each outer loop. The study of \(s\)-step KSMs shows that the convergence is often deteriorated for \(s>5\) due to the particular choice of the monomial basis.NEWLINENEWLINEThe authors describe and analyze a communication-avoiding conjugate gradients (CA-CG) algorithm and a communication-avoiding biconjugate gradients (CA-BICG) algorithm in finite precision. The goal is to bound the norm of the difference between the true and updated residual in terms of quantities which can be cheaply computed in each iteration. The residual replacement strategy applied is based on a technique developed by \textit{H. A. van der Vorst} and \textit{Q. Ye} [SIAM J. Sci. Comput. 22, No. 3, 835--852 (2000; Zbl 0983.65039)]. At the replacement steps, the updated residual is replaced with the true residual and then a group update is performed. The group update strategy ensures that the deviation of residuals remains bounded from the last replacement step to the final iteration by reducing the error in the local recurrence.NEWLINENEWLINESelected matrices both symmetric positive and nonsymmetric are tested. The authors use row and column scaling to equilibrate the input matrix \(A\), preserving symmetry for the symmetric positive definite case. Numerical experiments demonstrate that the strategy of residual replacement and group update strategy can improve the solution accuracy already for a small number of residual replacement steps.