The influence of relaxed supernode partitions on the multifrontal method
- 1 December 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 15 (4), 291-309
- https://doi.org/10.1145/76909.76910
Abstract
In this paper we present an algorithm for partitioning the nodes of a graph into supernodes, which improves the performance of the multifrontal method for the factorization of large, sparse matrices on vector computers. This new algorithm first partitions the graph into fundamental supernodes. Next, using a specified relaxation parameter, the supernodes are coalesced in a careful manner to create a coarser supernode partition. Using this coarser partition in the factorization generally introduces logically zero entries into the factor. This is accompanied by a decrease in the amount of sparse vector computations and data movement and an increase in the number of dense vector operations. The amount of storage required for the factor is generally increased by a small amount. On a collection of moderately sized 3-D structures, matrices speedups of 3 to 20 percent on the Cray X-MP are observed over the fundamental supernode partition which allows no logically zero entries in the factor. Using this relaxed supernode partition, the multifrontal method now factorizes the extremely sparse electric power matrices faster than the general sparse algorithm. In addition, there is potential for considerably reducing the communication requirements for an implementation of the multifrontal method on a local memory multiprocessor.Keywords
This publication has 15 references indexed in Scilit:
- Progress in Sparse Matrix Methods for Large Linear Systems On Vector SupercomputersThe International Journal of Supercomputing Applications, 1987
- On the storage requirement in the out-of-core multifrontal method for sparse factorizationACM Transactions on Mathematical Software, 1986
- A compact row storage scheme for Cholesky factors using elimination treesACM Transactions on Mathematical Software, 1986
- Modification of the minimum-degree algorithm by multiple eliminationACM Transactions on Mathematical Software, 1985
- Proposed sparse extensions to the Basic Linear Algebra SubprogramsACM SIGNUM Newsletter, 1985
- Squeezing the most out of an algorithm in CRAY FORTRANACM Transactions on Mathematical Software, 1984
- The Multifrontal Solution of Indefinite Sparse Symmetric LinearACM Transactions on Mathematical Software, 1983
- A New Implementation of Sparse Gaussian EliminationACM Transactions on Mathematical Software, 1982
- Sparse matrix test problemsACM SIGNUM Newsletter, 1982
- Full matrix techniques in sparse Gaussian eliminationPublished by Springer Science and Business Media LLC ,1982