James W. Demmel, Stanley C. Eisenstat, John R. Gilbert, Xiaoye S. Li and Joseph W.H. Liu

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-95-883
July 1995

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/CSD-95-883.pdf

We investigate several ways to improve the performance of sparse LU factorization with partial pivoting, as used to solve unsymmetric linear systems. To perform most of the numerical computation in dense matrix kernels, we introduce the notion of unsymmetric supernodes. To better exploit the memory hierarchy, we introduce unsymmetric supernode-panel updates and two-dimensional data partitioning. To speed up symbolic factorization, we use Gilbert and Peierls's depth-first search with Eisenstat and Liu's symmetric structural reductions. We have implemented 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 performance with UMFPACK, which uses a multifrontal approach; our code is usually faster.

BibTeX citation:

@techreport{Demmel:CSD-95-883,
    Author = {Demmel, James W. and Eisenstat, Stanley C. and Gilbert, John R. and Li, Xiaoye S. and Liu, Joseph W.H.},
    Title = {A Supernodal Approach to Sparse Partial Pivoting},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1995},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5830.html},
    Number = {UCB/CSD-95-883},
    Abstract = {We investigate several ways to improve the performance of sparse LU factorization with partial pivoting, as used to solve unsymmetric linear systems. To perform most of the numerical computation in dense matrix kernels, we introduce the notion of unsymmetric supernodes. To better exploit the memory hierarchy, we introduce unsymmetric supernode-panel updates and two-dimensional data partitioning. To speed up symbolic factorization, we use Gilbert and Peierls's depth-first search with Eisenstat and Liu's symmetric structural reductions. We have implemented 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 performance with UMFPACK, which uses a multifrontal approach; our code is usually faster.}
}

EndNote citation:

%0 Report
%A Demmel, James W.
%A Eisenstat, Stanley C.
%A Gilbert, John R.
%A Li, Xiaoye S.
%A Liu, Joseph W.H.
%T A Supernodal Approach to Sparse Partial Pivoting
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/CSD-95-883
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5830.html
%F Demmel:CSD-95-883