A new class of parallel alternating-type iterative methods (Q2564263)

Given a linear system \(Ax=b\), the alternating type methods considered in this paper rely on a decomposition \(A=H +V\) and a matrix \(\Sigma\). One iteration step consists of two half steps of the kind \((H+\rho \Sigma) u=f\) or \((V+ \rho' \Sigma) w=g\), where \(\rho\) and \(\rho'\) are parameters that change from step to step. The class of these methods comprises the classical Peaceman-Rachford ADI method as well as SSOR and USSOR. The basic idea of the paper is to replace \(m\) iterations of the serial process by a parallel process where \(m^2\) single steps are performed in parallel and the new global iterate is a linear combination of these \(m^2\) intermediate iterates. It is shown that in the case where all matrices \(H, V, \Sigma\) commute one can always choose the linear combination such that the \(m\)-th iterate of the serial process is obtained. Thus, ideally, wall clock time is reduced by a factor of \(m\) with the use of \(m^2\) processors. A numerical example on a workstation cluster under pvm illustrates the results.