Nested dissection on a mesh-connected processor array
Patrick H Worley, Robert Schreiber · Defense Technical Information Center (DTIC) · 1985
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.