Nested-Dissection Orderings for Sparse LU with Partial Pivoting
Nested-Dissection Orderings for Sparse LU with Partial Pivoting
复制标题
具有部分旋转的稀疏 LU 的嵌套剖析排序
DOI：
--
复制
发表时间：
2000
影响因子：
1.5
通讯作者：
Sivan Toledo
中科院分区：
文献类型：
--
作者：
Igor Brainman;Sivan Toledo
我们描述了一种新的填充最小化排序技术的执行和性能稀疏LU分解与部分枢轴。该技术由吉尔伯特和施赖伯在1980年提出，但从未实施和测试。像其他技术排序稀疏矩阵的LU与部分枢转，我们的新方法预先排序矩阵的列（行置换是由数值分解过程中的枢转序列选择）。也像其他方法一样，我们选择的列置换Q是最小化QT AT AQ的Cholesky因子中的填充的置换。与现有的列排序技术，这一切都依赖于最小程度的抽象，我们的新方法是基于嵌套解剖排序的AT A。然而，我们的算法从不计算ATA的表示，这可能是昂贵的。我们只处理A本身的表示。实验表明，该方法是有效的，它可以减少填充显着相对于现有的最好的方法。该方法减少了LU运行时间的一些非常大的矩阵（数以千万计的非零的因素）超过一个因素2。
We describe the implementation and performance of a novel fill-minimization ordering technique for sparse LU factorization with partial pivoting. The technique was proposed by Gilbert and Schreiber in 1980 but never implemented and tested. Like other techniques for ordering sparse matrices for LU with partial pivoting, our new method preorders the columns of the matrix (the row permutation is chosen by the pivoting sequence during the numerical factorization). Also like other methods, the column permutation Q that we select is a permutation that minimizes the fill in the Cholesky factor of QT AT AQ. Unlike existing column-ordering techniques, which all rely on minimum-degree heuristics, our new method is based on a nested-dissection ordering of AT A. Our algorithm, however, never computes a representation of ATA, which can be expensive. We only work with a representation of A itself. Our experiments demonstrate that the method is efficient and that it can reduce fill significanly relative to the best existing methods. The method reduces the LU running time on some very large matrices (tens of millions of nonzeros in the factors) by more than a factor of 2.