Acta Numerica

Research Article

Parallel numerical linear algebra

James W. Demmela1*, Michael T. Heatha2 and Henk A. van der Vorsta3

a1 Computer Science Division and Mathematics Department University of California at Berkeley Berkeley, CA 94720 USA E-mail: demmel@cs.berkeley.edu

a2 Department of Computer Science and National Center for Supercomputing Applications University of Illinois Urbana, IL 61801 USA E-mail: heath@ncsa.uiuc.edu

a3 Mathematical Institute Utrecht University Utrecht, The Netherlands E-mail: vorst@math.ruu.nl

Abstract

We survey general techniques and open problems in numerical linear algebra on parallel architectures. We first discuss basic principles of paralled processing, describing the costs of basic operations on parallel machines, including general principles for constructing efficient algorithms. We illustrate these principles using current architectures and software systems, and by showing how one would implement matrix multiplication. Then, we present direct and iterative algorithms for solving linear systems of equations, linear least squares problems, the symmetric eigenvalue problem, the nonsymmetric eigenvalue problem, and the singular value decomposition. We consider dense, band and sparse matrices.

Footnotes

* The author was supported by NSF grant ASC-9005933, DARPA contract DAAL03-91-C-0047 via a subcontract from the University of Tennessee administered by ARO, and DARPA grant DM28E04120 via a subcontract from Argonne National Laboratory. This work was partially performed during a visit to the Institute for Mathematics and its Applications at the University of Minnesota.

† The author was supported by DARPA contract DAAL03-91-C-0047 via a subcontract from the University of Tennessee administered by ARO.

‡ This work was supported in part by NCF/Cray Research University Grant CRG 92.03.