Communication analysis of the PIE and QIF algorithms on distributed memory architecture

Abstract

Gaussian elimination (GE) and LU factorisation (LU) are two well known methods used to solve systems of linear equations. Parallel versions of GE and LU have been developed and widely implemented on parallel computers. Here, two new parallel methods for matrix elimination and matrix factorisation are presented.

Parallel Implicit Elimination method (PIE) is a scheme that eliminates two matrix elements simultaneously. The Quadrant Interlocking Factorisation method (QIF) decomposes a matrix into two quadrant interlocking factors of “butterfly” form denoted by W and Z.

The solution of GE and LU methods involve a back substitution process which is sequential in nature. PIE and QIF offer a parallel solution called bidirectional substitution.

Here the performance of the PIE and QIF algorithms on a message-passing architecture is compared to that of the GE and LU methods respectively. The theoretical analysis of commu-nication within the algorithms revealed that the communication involved in PIE and QIF is half that of GE and LU.

Keywords:

• Implicit elimination
• quardant interlocking
• factorisation linear equations gaussion elimination
• LU fatorisation

C.R. Categories:

• G 1.3
• F 1.2

^*Universiti Sains Malaysia, Penang, Malaysia.

^†Nottingham Trent University, Nottingham U.K.

^*Universiti Sains Malaysia, Penang, Malaysia.

^†Nottingham Trent University, Nottingham U.K.

Notes

^*Universiti Sains Malaysia, Penang, Malaysia.

^†Nottingham Trent University, Nottingham U.K.