Parallel solution of dense linear systems using diagonalization methods

Abstract

We study the parallel implementation of two diagonalization methods for solving dense linear systems: the well known Gauss-Jordan method and a new one introduced by Huard. The number of arithmetic operations performed by the Huard method is the same as for Gaussian elimination, namely 2n ³/3, less than for the Jordan method, namely n ³. We introduce parallel versions of these methods, compare their performances and study their complexity. We assume a shared memory computer with a number of processors p of the order of n, the size of the problem to be solved, We show that the best parallel version for Jordan's method is by rows whereas the best one for Huard's method is by columns. Our main result states that for a small number of processors the parallel Huard method is faster than the parallel Jordan method and slower otherwise. The separation is obtained for p = 0.44n.

Keywords:

• Parallel numerical algorithms
• linear system solver
• Jordan method
• diagonalization methods
• parallel computational complexity

C.R. Categories:

• G.10
• F.2.1