Secondary Re-Ordering Methods for Parallel Partitioned Sparse Inverse Solutions
Fernando L. Alvarado · 1992
This paper compares ordering algorithms to reduce the number of serial steps required for parallel repeat solutions. These algorithms are applied after the initial application of a fill-reducing algorithm, and are called "secondary re-ordering" algorithms. One algorithm described in this paper optimally reduces the number of no-fill partitions in the partitioned inverse of the LDLTfactors of A. The algorithm computes the minimum number of subsets in the partition over all permutations of L which preserve the lower triangular structure of the matrix. The paper considers also a tree rotations method to reduce the height of the elimination tree. This paper describes experiments on the behavior of these algorithms when used in combination with a variety of primary ordering algorithms: minimum degree, multiple minimum degree, minimum length and nested dissection. Numerical results on power system and finite element matrices are presented. The main conclusion is that the primary re-ordering is more important than the secondary re-ordering method in increasing parallelism.