Skip to main content

Space and time efficient implementations of parallel nested dissection

Publication ,  Journal Article
Armon, D; Reif, J
Published in: 4th Annual ACM Symposium on Parallel Algorithms and Architectures
January 1, 1992

Nested dissection is a method for solving large sparse systems of linear equations. The method is inherently parallelizable and efficient algorithms for parallel nested dissection (PND) exist for various parallel architectures. Birkhoff and George showed that for a sparse grid graph, a parallel algorithm with n processors takes O(√n) parallel time. The algorithm in works on a PRAM model, using O(n3/2) processors and taking O((log n)3) time for a general class of matrices which have have O(√n) size separators. Both these algorithms use a logarithmic factor of space larger than the input matrix. Our results are as follows: (1) We describe a FAST PND algorithm for the PRAM model, which reduces the time bound from O((log n)3) to O((log n)2), without significantly increasing the processor bound. (2) We implement a PND algorithm that works on a mesh-connected processor array, using O(n) processors and taking O(√n) time for the important and more general case where the graph of the matrix is of constant degree and separator size √n (as required for many 2D PDE applications). (3) We describe a COMPACT PND algorithm which reduces the space bounds to a constant factor of the input matrix, without significant increase in time or processor bounds. In addition to these practical results, we show that it is theoretically possible to achieve tighter bounds on the amount of work performed (and thus on time and processor bounds), using known theoretical results about parallel matrix multiplication. Finally, we show that our algorithms generalize to solve all pairs minimal cost path problems within the same complexity.

Duke Scholars

Published In

4th Annual ACM Symposium on Parallel Algorithms and Architectures

DOI

Publication Date

January 1, 1992

Start / End Page

344 / 352
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Armon, D., & Reif, J. (1992). Space and time efficient implementations of parallel nested dissection. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 344–352. https://doi.org/10.1145/140901.141912
Armon, D., and J. Reif. “Space and time efficient implementations of parallel nested dissection.” 4th Annual ACM Symposium on Parallel Algorithms and Architectures, January 1, 1992, 344–52. https://doi.org/10.1145/140901.141912.
Armon D, Reif J. Space and time efficient implementations of parallel nested dissection. 4th Annual ACM Symposium on Parallel Algorithms and Architectures. 1992 Jan 1;344–52.
Armon, D., and J. Reif. “Space and time efficient implementations of parallel nested dissection.” 4th Annual ACM Symposium on Parallel Algorithms and Architectures, Jan. 1992, pp. 344–52. Scopus, doi:10.1145/140901.141912.
Armon D, Reif J. Space and time efficient implementations of parallel nested dissection. 4th Annual ACM Symposium on Parallel Algorithms and Architectures. 1992 Jan 1;344–352.

Published In

4th Annual ACM Symposium on Parallel Algorithms and Architectures

DOI

Publication Date

January 1, 1992

Start / End Page

344 / 352