Factoring matrices with a tree-structured sparsity pattern

Factoring matrices with a tree-structured sparsity pattern,10.1016/j.laa.2011.03.035,Linear Algebra and Its Applications,Alex Druinsky,Sivan Toledo

Factoring matrices with a tree-structured sparsity pattern  
BibTex | RIS | RefWorks Download
Let A be a matrix whose sparsity pattern is a tree with maximal degree dmax. We show that if the columns of A are ordered using minimum degree on A+A∗, then factoring A using a sparse LU with partial pivoting algorithm generates only O(dmaxn) fill, requires only O(dmaxn) operations, and is much more stable than LU with partial pivoting on a general matrix. We also propose an even more efficient and just-as-stable algorithm called sibling-dominant pivoting. This algorithm is a strict partial pivoting algorithm that modifies the column preordering locally to minimize fill and work. It leads to only O(n) work and fill. More conventional column pre-ordering methods that are based (usually implicitly) on the sparsity pattern of A∗A are not as efficient as the approaches that we propose in this paper.
Journal: Linear Algebra and Its Applications - LINEAR ALGEBRA APPL , vol. 435, no. 5, pp. 1099-1110, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.