Factoring matrices with a tree-structured sparsity pattern |
| |
Authors: | Alex Druinsky |
| |
Institution: | School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel |
| |
Abstract: | 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. |
| |
Keywords: | 65F50 65F05 15A23 |
本文献已被 ScienceDirect 等数据库收录! |
|