A parallel elimination algorithm for the solution of dense linear systems

Abstract

For the solution of an N × N linear system Ax = d, based on the folding method of Evans and Hatzopoulos [4] and by partitioning the system into r ² blocks each of size n × n (N = r n), in [3] we had described a parallel elimination method suitable for an r-processor machine. The serial arithmetical operations count for this algorithm is 0(1/3(3 − l/r)N ³) thereby the algorithm could perform with efficiency E _r = 2/(3 − 1/r); note that 2/3 ≤ E_r ≤ 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 0(2/3N ³), 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.

Keywords:

• Linear system
• dense
• elimination
• partitioning
• parallel implementation
• efficiency

C.R.Categories:

• G.1.3
• G.1.0

^* Department of Mathematics, Kuwait university, P.O. Box 5969, Safat, 13060, Kuwait.

^* Department of Mathematics, Kuwait university, P.O. Box 5969, Safat, 13060, Kuwait.

Notes

^* Department of Mathematics, Kuwait university, P.O. Box 5969, Safat, 13060, Kuwait.