Implementing linear algebra algorithms on high performance architectures

In this paper we consider the data distribution and data movement issues related to the solution of the basic linear algebra problems on high performance systems. The algorithms we discuss in details are the Gauss andGauss-Jordan methods for solving a system of linear equations, the Cholesky's algorithm for LL^T-factorization, and QR-factorization algorithm using Householder transformations. It is shown that all those algorithms can be executed efficiently on a parallel system with simple and regular links and with partial pivoting. Detailed implementations of the algorithms are described using a simple parallel language on a systolic-type architecture. Both the theoretical analysis and the simulation results show speedups close to the optimal on moderately large problems