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. https://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: https://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: |
| |||||||||
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: |
| |||||||||
DOI: | 10.1145/63047.63124 | |||||||||
Record Number: | CaltechAUTHORS:20170104-151837529 | |||||||||
Persistent URL: | https://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: | 11 Nov 2021 05:13 |
Repository Staff Only: item control page