The Parallel Solution of Systems of Linear Equationsusing Iterative Methods on Transputer Networks

Abstract. We present a study of the implementational aspects of iterativemethods to solve systems of linear equations on a transputer network. Both dense and sparse systems are considered.First we discuss the implementation of a set of distributed linear algebra subroutines which are used as building blocks for implementing the iterativemethods. We show that the use of loop-unrolling significantly increases the efficiency of these implementations. The effect of the sparsity of the matriceson the performance is analysed. Finally, serial and parallel implementations of a polynomial preconditionedConjugate Gradient method are presented. 1 Introduction We consider the solution of the non-singular system of N linear algebraic equations Ax = b: (1) Iterative methods for solving system (1) are attractive because their complexity is O(N 2),provided the number of iterations required for convergence is small compared t