Coding parallel algorithms is generally regarded as a formidable task. To make this task manageable in the arena of linear algebra algorithms, we have developed the Parallel Linear Algebra Package (PLAPACK), an infrastructure for coding such algorithms at a high level of abstraction. It is often believed that by raising the level of abstraction in this fashion, performance is sacrificed. Throughout, we have maintained that indeed there is a performance penalty, but that by coding at a higher level of abstraction, more sophisticated algorithms can be implemented, which allows high levels of performance to be regained. In this paper, we show this to be the case for the parallel solver package implemented using PLAPACK, which includes Cholesky, LU, and QR factorization based solvers for symmetric positive definite, general, and overdetermined systems of equations, respectively. Contributions of this paper include new parallel algorithms for these factorizations and performance results on a Cray T3E-600.

Over the past twenty years, dense linear algebra libraries have gone through three generations of public domain general purpose packages. In the seventies, the first generation of packages were EISPACK and LINPACK, which implemented a broad spectrum of algorithms for solving dense linear eigenproblems and dense linear systems. In the late eighties, the second generation package called LAPACK was developed. This package attains high performance in a portable fashion while also improving upon the functionality and robustness of LINPACK and EISPACK. Finally, since the early nineties, a third generation package which ports LAPACK to distributed memory networks of computers has been underway as part of the ScaLAPACK project.PLAPACK is a maturing fourth generation package which uses a more application-centric view of vector and matrix distribution, Physically Based Matrix Distribution. It also uses an "MPI-like" programming interface that hides distribution and indexing details in opaque objects, provides a natural layering in the library, and provides a straight-forward application interface. In this paper, we give an overview of the design of PLAPACK.