On the cost of sequential and parallel algorithms for solving linear system of equations

Abstract

In this paper two parallel algorithms for solving dense linear equations are discussed. The algorithms are based on LU-decomposition followed by forward and backward substitutions. The algorithms are numerically stable and have been tested on the Sequent Balance Machine with efficient utilization of all processors.

Keywords:

• LU-decomposition
• forward and backward substitutions
• MIMD machine
• multi-tasking
• theoretical and experimental cost

AMS Subject Classifications:

• 65F10
• 65F50