Abstract: This chapter discusses parallel dense matrix computations, in particular the solution of linear systems by LU decomposition with partial pivoting. A general Cartesian scheme is presented for the distribution of matrices. Based on BSP cost analysis, the square cyclic distribution is proposed as particularly suitable for matrix computations such as LU decomposition or Gaussian elimination. The chapter introduces two-phase broadcasting of vectors, which is a useful collective communication method for sending copies of matrix rows or columns to a group of processors. These techniques are demonstrated in the specific case of LU decomposition, but they are applicable to almost all parallel matrix computations. The performance of the parallel LU program is examined in detail using a graphical BSP profiler.

Keywords: Cartesian distribution, collective communication, cyclic distribution, dense matrix, Gaussian elimination, linear system, pivoting, profiler, two-phase broadcasting,