Towards a fast implementation of spectral nested dissectionWe describe the spectral nested dissection (SND) algorithm, a new algorithm for computing orderings appropriate for parallel factorization of sparse, symmetric matrices. The algorithm makes use of spectral properties of the Laplacian matrix associated with the given matrix to compute separators. We evaluate the quality of the spectral orderings with respect to several measures: fill, elimination tree height, height and weight balances of elimination trees, and clique tree heights. We use some very large structural analysis problems as test cases and demonstrate on these real applications (such as the Space Shuttle Solid Rocket Booster) that spectral orderings compare quite favorably with commonly used orderings, outperforming them by a wide margin for some of these measures. The only disadvantage of SND is its relatively long execution time. We will present some recent efforts to improve the execution time using both a multilevel and a hybrid approach. We use SND in computing a multifrontal numerical factorization with the different orderings on an eight processor Cray Y-MP and show its effectiveness. We believe that spectral nested dissection is a major breakthrough in terms of generating efficient sparse orderings for parallel machines.
Document ID
19950028512
Acquisition Source
Legacy CDMS
Document Type
Conference Paper
Authors
Pothen, Alex (Pennsylvania State Univ. University Park, PA, United States)
Simon, Horst D. (Computer Sciences Corp. Moffett Field, CA, United States)
Wang, Lie (Pennsylvania State Univ. University Park, PA, United States)
Barnard, Stephen T. (Cray Research, Inc. Moffett Field, CA, United States)