A PARALLEL ELIMINATION ALGORITHM FOR THE SOLUTION OF DENSE LINEAR-SYSTEMS

For the solution of an N x N linear system Ax = d, based on the foldin g method of Evans and Hatzopoulos [4] and by partitioning the system i nto r(2) blocks each of size n x n (N = rn), in [3] we had described a parallel elimination method suitable for an r-processor machine. The serial arithmetical operations count for this algorithm is O(1/3(3 - 1 /r)N-3) thereby the algorithm could perform with efficiency E(r) = 2/( 3 - 1/r); note that 2/3 less than or equal to E(r) less than or equal to 4/5. In the present paper we consider an alternative elimination pr ocedure together with the method of partitioning to obtain a parallel algorithm for the solution of dense linear systems. The serial arithme tical operations count for the present algorithm is O(2/3N(3)), which is of the same order as that for the standard Gaussian elimination met hod; thus the present algorithm could perform with efficiency close to 1 on a multiprocessor machine.