A supernodal approach to sparse partial pivoting
A supernodal approach to sparse partial pivoting
复制标题
DOI：
10.1137/s0895479895291765
复制
发表时间：
1999-07-13
影响因子：
1.5
通讯作者：
Liu, JWH
中科院分区：
文献类型：
--
作者：
Demmel, JW;Eisenstat, SC;Liu, JWH
我们研究了几种方法，以通过局部枢纽来提高稀疏LU分解的性能，以解决不对称的线性系统。我们介绍了不对称的超节点的概念，以执行密集矩阵内核中的大多数数值计算。我们介绍了不对称的超节点 - 面板更新和二维数据分区，以更好地利用内存层次结构。我们将吉尔伯特（Gilbert）和佩尔斯（Peierls）的深度优先搜索与Eisenstat和Liu的对称结构减少一起使用来加快符号分解。我们使用所有这些想法开发了稀疏的LU代码。我们提出了实验，表明它的速度明显比以前的部分旋转代码快得多。我们还将其性能与使用多尺寸方法的UMFPACK进行了比较。我们的代码在时间和存储要求上具有竞争力，尤其是对于大问题。
We investigate several ways to improve the performance of sparse LU factorization with partial pivoting, as used to solve unsymmetric linear systems. We introduce the notion of unsymmetric supernodes to perform most of the numerical computation in dense matrix kernels. We introduce unsymmetric supernode-panel updates and two-dimensional data partitioning to better exploit the memory hierarchy. We use Gilbert and Peierls's depth-first search with Eisenstat and Liu's symmetric structural reductions to speed up symbolic factorization.We have developed a sparse LU code using all these ideas. We present experiments demonstrating that it is significantly faster than earlier partial pivoting codes. We also compare its performance with UMFPACK, which uses a multifrontal approach; our code is very competitive in time and storage requirements, especially for large problems.