Systems of Linear Equations solved by Block Gauss Jordan Method using a Transputer Cube

Ole Tingleff / Section for Numerical Analysis

Abstract

This paper describes a method for solving syst ems of linear equations with parallel computations. The method is a block version of the Gauss Jordan method. The computations are performed on a network of 8 transputers connected as a cube. The communication system for the transputer cube is described.

1. Introduction In many computations treating application problems, a major part of the computer time is spent on the solution of systems of linear equations. This applies to, e.g. electrical fields, temperature distributions, resservoir simulation, stress - and stiffness computation, optimization, linear - and non-linear programming. Thus it is important that we have efficient methods for linear equations, and one of the means of achieving this is parallel programming.
The method chosen is the Gauss-Jordan elimination method for full, general matrices. Row operations below and above the diagonal position in the matrix transform the system into one with a diagonal matrix. From this, we can easily find the solution of the system. In the parallel implementation we send a block of complete rows to each of the transputers of the system, and thus the method is based on block row operations.
It is charateristic of the method that during the computations each processor produces a block of intermediate results which must be broadcast to all the othe r processors. Thus it is important that the distance from any processor to any oth er processor is minimal. A cube structured transputer network is appropriate for this situation and we have chosen to use a cube with 8 transputers.
The automatic communication harness for the transputer cube is described. It is based on the prototype harness presented at the NTUG'93 meeting. It has been organised so that it is easy to reuse the harness for an other computational problem. The programning language is occam 2, running under the occam 2 toolset.

IMM Technical Report 8/95