PARALLEL ALGORITHMS IN LINEAR ALGEBRA

RICHARD P. BRENT

Abstract

This paper provides an introduction to algorithms for fundamental linear algebra problems on various parallel computer architectures, with the emphasis on distributed-memory MIMD machines. To illustrate the basic concepts and key issues, we consider the problem of parallel solution of a nonsingular linear system by Gaussian elimination with partial pivoting. This problem has come to be regarded as a benchmark for the performance of parallel machines. We consider its appropriateness as a benchmark, its communication requirements, and schemes for data distribution to facilitate communication and load balancing. In addition, we describe some parallel algorithms for orthogonal (QR) factorization and the singular value decomposition (SVD).

Comments

Only the Abstract is given here. The full paper will appear as [1].

References

1. R. P. Brent, “Parallel algorithms in linear algebra”, Proceedings Second NEC Research Symposium (Tsukuba, Japan, August 1991), invited paper, to appear. Available as Report TR-CS-91-06, Computer Sciences Laboratory, ANU, August 1991, 17 pp. rpb128.

Computer Sciences Laboratory, Australian National University, Canberra, ACT 0200 E-mail address: rpb@cslab.anu.edu.au

rpb128a typeset using AMS-L^{A}TEX

1991 Mathematics Subject Classification. Primary 65Y05; Secondary 65F05, 65F15, 65F25, 65F30, 65Y10.

Key words and phrases. Linear algebra, parallel algorithms, distributed memory, local memory, message passing, MIMD, Gaussian elimination, blocking, load balancing, data distribution, scattered storage.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1991, 1993, R. P. Brent.