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 folding method of Evans and Hatzopoulos [4] and by partitioning the system into 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 procedure together with the method of partitioning to obtain a parallel algorithm for the solution of dense linear systems. The serial arithmetical operations count for the present algorithm is O(2/3N(3)), which is of the same order as that for the standard Gaussian elimination method; thus the present algorithm could perform with efficiency close to 1 on a multiprocessor machine.