A FAST REORDERING ALGORITHM FOR PARALLEL SPARSE TRIANGULAR SOLUTION

作     者：POTHEN, A ALVARADO, FL 

作者机构：UNIV WISCONSINDEPT COMP SCIMADISONWI 53706 UNIV WISCONSINDEPT MATHMADISONWI 53706 UNIV WISCONSINDEPT ELECT & COMP ENGN1425 JOHNSON AVEMADISONWI 53706 

出 版 物：《SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING》 (工业与应用数学会科学计算杂志)

年 卷 期：1992年第13卷第2期

页      面：645-653页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：DIRECTED ACYCLIC GRAPH ELIMINATION TREE MASSIVELY PARALLEL COMPUTERS REORDERING ALGORITHM SPARSE CHOLESKY FACTORIZATION SPARSE TRIANGULAR SYSTEMS TRANSITIVE REDUCTION 

摘      要：A space-efficient partitioned representation of the inverse of a unit lower triangular matrix L may be used for efficiently solving sparse triangular systems on massively parallel computers. The number of steps required in the parallel triangular solution is equal to the number of subsets of elementary triangular matrices in the partitioned representation of the inverse. Alvarado and Schreiber have recently described two partitioning algorithms that compute the minimum number of subsets in the partition over all permutations of L which preserve the lower triangular structure of the matrix. Their algorithms require space linear and time nonlinear in the number of nonzeros in L. This paper describes a partitioning algorithm that requires only O(n) time and space for computing an optimal partition, when L is restricted to be a Cholesky factor. (Here n is the order of L.) The savings result from the observation that instead of working with the structure of L, it is sufficient to work with its transitive reduction, the elimination tree of L. Experimentally the new partitioning algorithm requires negligible time in comparison to the previous partitioning algorithms and to the Multiple-Minimum-Degree ordering algorithm.