A generalization of s-step variants of gradient methods

The s-step methods were proposed by Chronopoulos to gain efficiency in parallel programming of iterative methods for linear systems. They are variants of classical iterative methods based on the construction of a Krylov subspace basis on each iteration. These s-step methods were inferred from algorithms like the Conjugate Gradient, Generalized Conjugate Residual or the Minimal Residual. They converge for all symmetric, nonsymmetric definite and some nonsymmetric indefinite matrices. In this paper, we introduce an s-step variant of a General Orthogonalization Algorithm, that is, a generalization of s-step variants of gradient methods. We prove convergence and obtain error estimates. We also describe an Orthomin variant, together with a convergence theorem. From this we derive the well known s-step methods as particular cases, and some which are newfound to our knowledge. This provides a unified framework to derive and study s-step methods. Some of the methods obtained are convergent for every nonsingular matrix. Finally, we give some numerical results for the new proposed methods, showing that the parallel implementation of these overcomes the original ones.

keywords: Iterative methods, s-step, Large linear systems, Krylov subspace