The influence of relaxed supernode partitions on the multifrontal method
作者： Cleve Ashcraft , Roger Grimes
DOI: 10.1145/76909.76910
关键词:
摘要: In this paper we present an algorithm for partitioning the nodes of a graph into supernodes, which improves performance multifrontal method factorization large, sparse matrices on vector computers. This new first partitions fundamental supernodes. Next, using specified relaxation parameter, supernodes are coalesced in careful manner to create coarser supernode partition. Using partition generally introduces logically zero entries factor. is accompanied by decrease amount computations and data movement increase number dense operations. The storage required factor increased small amount. On collection moderately sized 3-D structures, speedups 3 20 percent Cray X-MP observed over allows no relaxed partition, now factorizes extremely electric power faster than general algorithm. addition, there potential considerably reducing communication requirements implementation local memory multiprocessor.
acm.org
sci-hub.se 参考文章(19)
Iain S. Duff, Full matrix techniques in sparse Gaussian elimination Lecture Notes in Mathematics. pp. 71- 84 ,(1982) , 10.1007/BFB0093150
S C Eisenstat, M H Schultz, A H Sherman, Software for Sparse Gaussian Elimination with Limited Core Storage. ,(1978)
Alan George, Joseph W. Liu, Computer Solution of Large Sparse Positive Definite Prentice Hall Professional Technical Reference. ,(1981)
Joseph E. Pasciak, Alan George, Joseph W. Liu, Computer solution of large sparse positive definite systems Mathematics of Computation. ,vol. 39, pp. 305- ,(1982) , 10.2307/2007640
Joseph W. H. Liu, On the storage requirement in the out-of-core multifrontal method for sparse factorization ACM Transactions on Mathematical Software. ,vol. 12, pp. 249- 264 ,(1986) , 10.1145/7921.11325
I. S. Duff, J. K. Reid, The Multifrontal Solution of Unsymmetric Sets of Linear Equations SIAM Journal on Scientific and Statistical Computing. ,vol. 5, pp. 633- 641 ,(1984) , 10.1137/0905045
David S. Dodson, John G. Lewis, Proposed sparse extensions to the Basic Linear Algebra Subprograms ACM SIGNUM Newsletter. ,vol. 20, pp. 22- 25 ,(1985) , 10.1145/1057935.1057938
Iain Duff, Roger Grimes, John Lewis, Bill Poole, Sparse matrix test problems ACM SIGNUM Newsletter. ,vol. 17, pp. 22- 22 ,(1982) , 10.1145/1057588.1057590
C. Cleveland Ashcraft, Roger G. Grimes, John G. Lewis, Barry W. Peyton, Horst D. Simon, Petter E. Bjørstad, Progress in Sparse Matrix Methods for Large Linear Systems On Vector Supercomputers ieee international conference on high performance computing data and analytics. ,vol. 1, pp. 10- 30 ,(1987) , 10.1177/109434208700100403
Iain S. Duff, Parallel implementation of multifrontal schemes parallel computing. ,vol. 3, pp. 193- 204 ,(1986) , 10.1016/0167-8191(86)90019-0