A projection method for solving nonsymmetric linear systems on multiprocessors (Q1118356)

For the solution of nonsingular linear \(n\times n\) systems, the method of \textit{S. Kaczmarz} [Bull. Int. Acad. Polon. Sci. A 1937, 355-357 (1937; Zbl 0017.31703)] is considered. The authors organize this method in a block SSOR manner, show the optimal iteration parameter to be 1, and accelerate it by an outer conjugate gradient iteration. This leads to a method in which in every step a linear least squares problem has to be solved. If the latter can be broken up into independent least squares problems, a multiprocessor algorithm arises. It is shown how to do this for block tridiagonal systems. On a CRAY X-MP with one CPU and for discretized 2D elliptic equations, the method has been compared with those from the Yale PCGPAK and found to be more reliable. On a 4-processor CRAY X-MP, a speedup rate of 3.6 has been obtained.