A Supernodal Approach to Sparse Partial Pivoting

A Supernodal Approach to Sparse Partial Pivoting

July 10, 1995 | James W. Demmel, Stanley C. Eisenstat, John R. Gilbert, Xiaoye S. Li, Joseph W. H. Liu
This paper presents a supernodal approach to sparse LU factorization with partial pivoting for unsymmetric linear systems. The authors introduce unsymmetric supernodes, which group columns with similar nonzero structures to enable efficient dense matrix operations. They also use unsymmetric supernode-panel updates and two-dimensional data partitioning to better exploit memory hierarchy. Symbolic factorization is accelerated using depth-first search and symmetric structural reductions. The resulting code, SUPERLU, is significantly faster than earlier partial pivoting codes and outperforms UMFPACK, which uses a multifrontal approach. The paper describes the definition and implementation of unsymmetric supernodes, which generalize the symmetric concept to allow for more efficient numeric factorization. The authors analyze different supernode definitions (T1-T5) and conclude that T2 or T3 are most effective. They also discuss storage strategies for supernodes and the use of column elimination trees to determine supernode boundaries. The paper presents a detailed algorithm for supernodal numeric factorization, including supernode-column and supernode-panel updates. These updates are optimized using BLAS kernels and memory locality techniques. The authors also describe symbolic factorization, which determines which supernodes update which columns and helps in pruning redundant structural information. The paper includes experimental results showing that the SUPERLU code is significantly faster than other column and submatrix codes. It also investigates cache behavior and demonstrates that the code's performance is largely unaffected by the order of updates. The authors conclude that supernodal techniques can significantly improve the performance of unsymmetric solvers, and that the SUPERLU code provides an efficient and effective solution for sparse LU factorization with partial pivoting.This paper presents a supernodal approach to sparse LU factorization with partial pivoting for unsymmetric linear systems. The authors introduce unsymmetric supernodes, which group columns with similar nonzero structures to enable efficient dense matrix operations. They also use unsymmetric supernode-panel updates and two-dimensional data partitioning to better exploit memory hierarchy. Symbolic factorization is accelerated using depth-first search and symmetric structural reductions. The resulting code, SUPERLU, is significantly faster than earlier partial pivoting codes and outperforms UMFPACK, which uses a multifrontal approach. The paper describes the definition and implementation of unsymmetric supernodes, which generalize the symmetric concept to allow for more efficient numeric factorization. The authors analyze different supernode definitions (T1-T5) and conclude that T2 or T3 are most effective. They also discuss storage strategies for supernodes and the use of column elimination trees to determine supernode boundaries. The paper presents a detailed algorithm for supernodal numeric factorization, including supernode-column and supernode-panel updates. These updates are optimized using BLAS kernels and memory locality techniques. The authors also describe symbolic factorization, which determines which supernodes update which columns and helps in pruning redundant structural information. The paper includes experimental results showing that the SUPERLU code is significantly faster than other column and submatrix codes. It also investigates cache behavior and demonstrates that the code's performance is largely unaffected by the order of updates. The authors conclude that supernodal techniques can significantly improve the performance of unsymmetric solvers, and that the SUPERLU code provides an efficient and effective solution for sparse LU factorization with partial pivoting.
Reach us at info@futurestudyspace.com