A fast algorithm for reordering sparse matrices for parallel factorization
A fast algorithm for reordering sparse matrices for parallel factorization
复制标题
一种用于并行分解的稀疏矩阵重新排序的快速算法
DOI：
10.1137/0910070
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
A. Pothen
中科院分区：
文献类型：
--
作者：
J. G. Lewis;B. Peyton;A. Pothen
杰斯和基斯[IEEE Transans.Comput.，C-31(1982)，pp.231-239]介绍了一种对稀疏对称矩阵A进行排序的方法，以实现有效的并行分解。并行排序分两步计算。首先，矩阵A通过某种填充归约排序进行排序。其次，通过使用初始填充减少排序对A进行符号分解而得到的填充图，计算出A的并行排序。在填充位于填充图中的所有排序中，这种并行排序在因式分解中实现了最少的并行步骤。Jess和Kees没有为该方案的任一步骤指定算法的实现细节。Liu和Mirzaian[SIAM J.Display Math.，2(1989)，pp.100-107]设计了一个实现第二步的算法，但它的时间和空间要求高于计算常见的填充缩减排序的成本。提出了一种利用弦图的团树表示来实现并行排序的快速算法。并行排序步骤的成本远低于填充减少步骤的成本。该算法的时间和空间复杂度与L的压缩下标个数呈线性关系，即填充图的最大团的大小之和。实验证明，运行时间与Liu的启发式复合旋转算法几乎相同，该算法近似于最小并行步数。
Jess and Kees [IEEE Trans. Comput., C-31 (1982), pp. 231–239] introduced a method for ordering a sparse symmetric matrix A for efficient parallel factorization. The parallel ordering is computed in two steps. First, the matrix A is ordered by some fill-reducing ordering. Second, a parallel ordering of A is computed from the filled graph that results from symbolically factoring A using the initial fill-reducing ordering. Among all orderings whose fill lies in the filled graph, this parallel ordering achieves the minimum number of parallel steps in the factorization of A. Jess and Kees did not specify the implementation details of an algorithm for either step of this scheme. Liu and Mirzaian [SIAM J. Discrete Math., 2 (1989), pp. 100–107] designed an algorithm implementing the second step, but it has time and space requirements higher than the cost of computing common fill-reducing orderings.A new fast algorithm that implements the parallel ordering step by exploiting the clique tree representation of a chordal graph is presented. The cost of the parallel ordering step is reduced well below that of the fill-reducing step. This algorithm has time and space complexity linear in the number of compressed subscripts for L, i.e., the sum of the sizes of the maximal cliques of the filled graph. Running times nearly identical to Liu's heuristic composite rotations algorithm, which approximates the minimum number of parallel steps, are demonstrated empirically.