Factoring matrices with a tree-structured sparsity pattern (Q551257): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: UMFPACK / rank | |||
Normal rank |
Revision as of 17:11, 28 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Factoring matrices with a tree-structured sparsity pattern |
scientific article |
Statements
Factoring matrices with a tree-structured sparsity pattern (English)
0 references
15 July 2011
0 references
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.
0 references
sibling-dominant pivoting
0 references
tree-structured matrices
0 references
minimum degree ordering
0 references
sparse matrices
0 references
sparse LU-factorization
0 references
algorithm
0 references
column ordering
0 references
numerical experiments
0 references