**SOFTWARE LIBRARIES FOR LINEAR ALGEBRA
COMPUTATIONS ON HIGH PERFORMANCE COMPUTERS**

Jack J. Dongarra

David W. Walker

**Abstract**

This paper discusses the design of linear algebra libraries for high performance computers. Particular emphasis is placed on the development of scalable algorithms for MIMD distributed memory concurrent computers. A brief description of the EISPACK, LINPACK, and LAPACK libraries is given, followed by an outline of ScaLAPACK, which is a distributed memory version of LAPACK currently under development. The importance of block-partitioned algorithms in reducing the frequency of data movement between different levels of hierarchical memory is stressed. The use of such algorithms helps reduce the message startup costs on distributed memory concurrent computers. Other key ideas in our approach are the use of distributed versions of the Level 3 Basic Linear Algebra Subprograms (BLAS) as computational building blocks, and the use of Basic Linear Algebra Communication Subprograms (BLACS) as communication building blocks. Together the distributed BLAS and the BLACS can be used to construct higher-level algorithms, and hide many details of the parallelism from the application developer.

The block-cyclic data distribution is described, and adopted as a good way of distributing block-partitioned matrices. Block-partitioned versions of the Cholesky and LU factorizations are presented, and optimization issues associated with the implementation of the LU factorization algorithm on distributed memory concurrent computers are discussed, together with its performance on the Intel Delta system. Finally, approaches to the design of library interfaces are reviewed.

**Key words:**Parallel computing, linear algebra software libraries,
LAPACK, ScaLAPACK

**AMS subject classifications:**65Y05, 65Y10, 65F05

- Introduction
- The BLAS as the Key to Portability
- Block Algorithms and Their Derivation
- LU Factorization
- Data Distribution
- Parallel Implementation
- Optimization, Tuning, and Trade-offs
- Conclusions and Future Research Directions
- References
- About this document ...

Sun Feb 9 10:05:05 EST 1997