COMMUNICATION ANALYSIS OF THE PIE AND QIF ALGORITHMS ON DISTRIBUTED-MEMORY ARCHITECTURE

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 co mputers. Here, two new parallel methods for matrix elimination and mat rix factorisation are presented.Parallel Implicit Elimination method ( PIE) is a scheme that eliminates two matrix elements simultaneously. T he Quadrant Interlocking Factorisation method (QIF) decomposes a matri x into two quadrant interlocking factors of ''butterfly'' form denoted by W and Z. The solution of GE and LU methods involve a back substitu tion process which is sequential in nature. PIE and QIF offer a parall el solution called bidirectional substitution. Here the performance of the PIE and QIF algorithms on a message-passing architecture is compa red to that of the GE and LU methods respectively. The theoretical ana lysis of communication within the algorithms revealed that the communi cation involved in PIE and QIF is half that of GE and LU.