A parallel row projection solver for large sparse linear systems

In this paper we present a parallel iterative solver for large and sparse nonsymmetric linear systems. The solver is based on a row-projection algorithm, derived from the symmetrized block version of the Kaczmarz method with Conjugate Gradient acceleration. A comparison with some Krylov subspace methods shows the remarkable robustness of this algorithm when applied to systems with eigenvalues arbitrarily distributed in the complex plane. The parallel version of the algorithm was developed for MIMD distributed memory machines and it is based on a row partitioning approach which allows to compute each iteration as a simultaneous set of independent least squares problems. Moreover, we propose a data distribution strategy leading to a scalable communication scheme. The algorithm has been tested both on a system Intel iPSC/860 and on the Intel Touchstone DELTA System, running the Intel NX message passing environment