The theoretical cost of sequential and parallel algorithms for solving linear systems of equations (Q1367427)

The purpose of this paper is to give new sequential and parallel algorithms for solving linear systems of equations using the LU-decomposition and block LU-decomposition algorithms followed by forward and backward substitution, and to compute the theoretical costs of these algorithms. It is shown that the theoretical cost of the block LU-decomposition algorithm is less than the cost of the LU-decomposition algorithm. The algorithms have been tested on the sequent balance machine.