CaltechAUTHORS
  A Caltech Library Service

LU decomposition of banded matrices and the solution of linear systems on hypercubes

Walker, D. W. and Aldcroft, T. and Cisneros, A. and Fox, G. C. and Furmanski, W. (1988) LU decomposition of banded matrices and the solution of linear systems on hypercubes. In: C3P Proceedings of the third conference on Hypercube concurrent computers and applications. Vol.2. ACM , New York, NY, pp. 1635-1655. ISBN 0-89791-278-0. http://resolver.caltech.edu/CaltechAUTHORS:20170104-151837529

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170104-151837529

Abstract

We describe the solution of linear systems of equations, Ax = b, on distributed-memory concurrent computers whose interconnect topology contains a two-dimensional mesh. A is assumed to be an M×M banded matrix. The problem is generalized to the case in which there are nb distinct right-hand sides, b, and can thus be expressed as AX = B, where X and B are both M×nb matrices. The solution is obtained by the LU decomposition method which proceeds in three stages: (1) LU decomposition of the matrix A, (2) forward reduction, (3) back substitution. Since the matrix A is banded a simple rectangular subblock decomposition of the matrices A, X, and B over the nodes of the ensemble results in excessive load imbalance. A scattered decomposition is therefore used to decompose the data. The sequential and concurrent algorithms are described in detail, and models of the performance of the concurrent algorithm are presented for each of the three stages of the algorithm. In order to ensure numerical stability the algorithm is extended to include partial pivoting. Performance models for the pivoting case are also given. Results from a 128-node Caltech/JPL Mark II hypercube are presented, and the performance models are found to be a good agreement with these data. Indexing overhead was found to contribute significantly to the total concurrent overhead.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/63047.63124DOIArticle
http://dl.acm.org/citation.cfm?doid=63047.63124PublisherArticle
Additional Information:© 1988 ACM. It is a pleasure to acknowledge the helpful and informative comments of Professor S. Lennart Johnsson of Yale University. This work is partially funded by the Department of Energy under grant number DE-FG03-85ER25009.
Funders:
Funding AgencyGrant Number
Department of Energy (DOE)DE-FG03-85ER25009
Record Number:CaltechAUTHORS:20170104-151837529
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170104-151837529
Official Citation:D. W. Walker, T. Aldcroft, A. Cisneros, G. C. Fox, and W. Furmanski. 1989. LU decomposition of banded matrices and the solution of linear systems on hypercubes. In Proceedings of the third conference on Hypercube concurrent computers and applications - Volume 2 (C3P), Geoffrey Fox (Ed.), Vol. 2. ACM, New York, NY, USA, 1635-1655. DOI=http://dx.doi.org/10.1145/63047.63124
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73229
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:04 Jan 2017 23:50
Last Modified:04 Jan 2017 23:50

Repository Staff Only: item control page