## Parallel algorithms in linear algebra

128. R. P. Brent,
Parallel algorithms in linear algebra,
* Algorithms and Architectures:
Proceedings of the Second NEC Research Symposium*
held at Tsukuba, Japan, August 1991 (edited by T. Ishiguro),
SIAM, Philadelphia, 1993, 54-72.
Also Technical Report TR-CS-91-06,
Computer Sciences Laboratory, ANU, August 1991, 17 pp.
arXiv:1004.5437v1
Abstract:
dvi (2K),
pdf (59K),
ps (25K).

Technical Report:
dvi (30K),
pdf (149K),
ps (78K).

Transparencies:
pdf (94K),
ps (52K).

## 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).

Go to next publication

Return to Richard Brent's index page