Nested Dissection on a Mesh-Connected Processor Array,
Abstract
We present a parallel implementation of Gaussian elimination without pivoting using the nested dissection ordering for solving Ax=b where A is an N x N symmetric positive definite matrix. If the graph of A is a square root of N x square root of N finite element mesh then Birkhoff and George and Liu have shown that a parallel complexity of 0 (Square root of N) can be achieved for Gaussian elimination with the nested dissection ordering. Our implementation achieves this parallel complexity on a two dimensional MIMD processor array with N processors and nearest neighbors interconnections. Thus nested dissection is a near optimal algorithm for this problem on this interconnection topology. The parallel implementation on this architecture requires 158 square root of N + 0 (log of square root of N to base 2) parallel floating point multiplications. It is faster than a Kung-Leiserson systolic array for banded matrices for N greater than or equal to 961, and faster than a serial implementation for N as small as 9.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1985
- Accession Number
- ADA154088
Entities
People
- P. H. Worley
- R. Schreiber
Organizations
- Stanford University