s-step iterative methods for symmetric linear systems (Q1118971)

The authors introduce and study the s-step conjugate gradient (CG) method for solving systems \(Ax=b\) of linear algebraic equations with a symmetric and positive definite system matrix A. In the s-step CG-method, the new iterate \(x_{i+1}=x_ ia^ 1_ ip^ 1_ i+...+a^ s_ ip^ s_ i\) is defined by minimizing the A-energy norm \(\| x_{i+1}-x\|_ A\) of the iteration error over \(\{x_ i+\sum^{s}_{j=1}a^ j_ ip^ j_ i\}\), where the search directions \(p^ j_ i=A^{j-1}r_ i+\sum^{s}_{k=1}b_{i-1}^{(j,k)}p^ k_{i-1}\), \(j=1,2,...,s\), are forced to be A-orthogonal to the preceding s directions, where \(r_ i=f-Ax_ i.\) From a theoretical point of view, s steps of the classical CG method are identical to one step of the s-step CG-method. However, there are several advantages of the s-step CG-method over the classical CG-method for parallel processing, e.g. a more appropriate data access and the simultaneous calculation of 2s inner products. In analogy to the s-step CG-method, the authors also discuss the s-step conjugate residual method. Stability investigations are made with respect to s. Finally, the authors present some numerical results in order to show the speed-up obtained on the multiprocessor system ALLIANT FX/8.