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§
The paper introduces a supernodal approach to sparse LU factorization with partial pivoting, aimed at improving the performance of solving unsymmetric linear systems. The authors propose several enhancements, including the use of unsymmetric supernodes, unsymmetric supernode-panel updates, and two-dimensional data partitioning to better exploit the memory hierarchy. They also employ depth-first search and symmetric structural reductions to speed up symbolic factorization. The resulting code, SUPERLU, is implemented and tested on various matrices, demonstrating significantly faster performance compared to earlier partial pivoting codes and UMFPACK, a multifrontal approach. The paper includes detailed descriptions of the algorithms, experimental results, and comparisons with other methods.The paper introduces a supernodal approach to sparse LU factorization with partial pivoting, aimed at improving the performance of solving unsymmetric linear systems. The authors propose several enhancements, including the use of unsymmetric supernodes, unsymmetric supernode-panel updates, and two-dimensional data partitioning to better exploit the memory hierarchy. They also employ depth-first search and symmetric structural reductions to speed up symbolic factorization. The resulting code, SUPERLU, is implemented and tested on various matrices, demonstrating significantly faster performance compared to earlier partial pivoting codes and UMFPACK, a multifrontal approach. The paper includes detailed descriptions of the algorithms, experimental results, and comparisons with other methods.
Reach us at info@study.space