Basic techniques for numerical linear algebra on bulk synchronous parallel computers

The bulk synchronous parallel (BSP) model promises scalable and portable software for a wide range of applications. A BSP computer consists of several processors, each with private memory, and a communi-cation network that delivers access to remote memory in uniform time. Numerical linear algebra computations can benet from the BSP model, both in terms of simplicity and eciency. Dense LU decomposition and other computations can be made more ecient by using the new tech-nique of two-phase randomised broadcasting, which is motivated by a cost analysis in the BSP model. For LU decomposition with partial pivoting, this technique reduces the communication time by a factor of ( p p+1)=3, where p is the number of processors. Theoretical analysis, together with benchmark values for machine pa-rameters, can be used to predict execution time. Such predictions are veri ed by numerical experiments on a 64-processor Cray T3D. The ex-perimental results conrm the advantage of two-phase randomised broad-casting.