Factoring matrices with a tree-structured sparsity pattern (Q551257)

The paper deals with factoring matrices whose sparsity pattern is a tree with maximal degree \(d_{\max}\). At first, the conventional sparse LU-factorization with partial pivoting and an effective column ordering is analyzed. The basic idea is to eliminate a leaf in each step that results in a variant of the minimum degree ordering algorithm. It is proven that this process requires \(\mathcal{O}(d_{\max}n)\) arithmetic operations and generates the same fill. At second, it is shown that the work and fill can be reduced to \(\mathcal{O}(n)\) using a more sophisticated ordering strategy called \textit{sibling-dominant pivoting}. In this algorithm, the column ordering depends on the numerical values of the matrix, not only on the structure of its graph. Furthermore, this ordering is built dynamically as the algorithm progresses, not as a preprocessing step. It is also proven that the growing factor in both algorithms is \(d_{\max}+1\) that is much smaller bound than the \(2^{n-1}\) bound for the general LU-factorization with partial pivoting. The numerical experiments demonstrate the theoretical results on academic problems given by almost-complete regular trees. The paper is well-written, interesting and instructive. The results have consequences whose significance may transcend the class of tree-structured matrices. First, the results show that there are classes of matrices on which a specific type of the ordering leads to the better efficiency. Second, they show that dynamic but cheap-to-compute local column reordering can dramatically reduce fill and work.