Parallel unsymmetric-pattern multifrontal sparse LU with column preordering

ABSTRACT

We present a new parallel sparse LU factorization algorithm and code. The algorithm uses a column-preordering partial-pivoting unsymmetric-pattern multifrontal approach. Our baseline sequential algorithm is based on UMFPACK 4, but is somewhat simpler and is often somewhat faster than UMFPACK version 4.0. Our parallel algorithm is designed for shared-memory machines with a small or moderate number of processors (we tested it on up to 32 processors). We experimentally compare our algorithm with SuperLU_MT, an existing shared-memory sparse LU factorization with partial pivoting. SuperLU_MT scales better than our new algorithm, but our algorithm is more reliable and is usually faster. More specifically, on matrices that are costly to factor, our algorithm is usually faster on up to 4 processors, and is usually faster on 8 and 16. We were not able to run SuperLU_MT on 32. The main contribution of this article is showing that the column-preordering partial-pivoting unsymmetric-pattern multifrontal approach, developed as a sequential algorithm by Davis in several recent versions of UMFPACK, can be effectively parallelized.

REFERENCES

• 1: Patrick R. Amestoy , Chiara Puglisi, An Unsymmetrized Multifrontal LU Factorization, SIAM Journal on Matrix Analysis and Applications, v.24 n.2, p.553-569, 2002 [doi>10.1137/S0895479800375370]
• 2: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 3: Cleve Ashcraft , Roger Grimes, The influence of relaxed supernode partitions on the multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.15 n.4, p.291-309, Dec. 1989 [doi>10.1145/76909.76910]
• 4: Igor Brainman , Sivan Toledo, Nested-Dissection Orderings for Sparse LU with Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.23 n.4, p.998-1012, 2001 [doi>10.1137/S0895479801385037]
• 5: Davis, T. A. 2003. A column pre-ordering strategy for the unsymmetric-pattern multifrontal method. Tech. Rep. TR-03-006, Department of Computer and Information Science and Engineering, University of Florida. May.
• 6: Timothy A. Davis, A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.165-195, June 2004 [doi>10.1145/992200.992205]
• 7: Davis, T. A. and Duff, I. S. 1991. Unsymmetric-pattern multifrontal methods for parallel sparse LU factorization. Tech. Rep. TR-91-023, Department of Computer and Information Science and Engineering, University of Florida. Jan.
• 8: Timothy A. Davis , Iain S. Duff, An Unsymmetric-Pattern Multifrontal Method for Sparse LU Factorization, SIAM Journal on Matrix Analysis and Applications, v.18 n.1, p.140-158, Jan. 1997 [doi>10.1137/S0895479894246905]
• 9: Timothy A. Davis , Iain S. Duff, A combined unifrontal/multifrontal method for unsymmetric sparse matrices, ACM Transactions on Mathematical Software (TOMS), v.25 n.1, p.1-20, March 1999 [doi>10.1145/305658.287640]
• 10: Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.377-380, September 2004 [doi>10.1145/1024074.1024080]
• 11: Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, A column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.353-376, September 2004 [doi>10.1145/1024074.1024079]
• 12: James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
• 13: James W. Demmel , John R. Gilbert , Xiaoye S. Li, An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.915-952, Oct. 1999 [doi>10.1137/S0895479897317685]
• 14: James W. Demmel , John R. Gilbert , Xiaoye S. Li, An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.915-952, Oct. 1999 [doi>10.1137/S0895479897317685]
• 15: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 16: I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 [doi>10.1145/356044.356047]
• 17: Stanley C. Eisenstat , Joseph W. H. Liu, Exploiting structural symmetry in a sparse partial pivoting code, SIAM Journal on Scientific Computing, v.14 n.1, p.253-257, Jan. 1993 [doi>10.1137/0914016]
• 18: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, ACM SIGPLAN Notices, v.33 n.5, p.212-223, May 1998
• 19: Alan George , Esmond Ng, Symbolic factorization for sparse Gaussian elimination with partial pivoting, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.877-898, November 1, 1987 [doi>10.1137/0908072]
• 20: John Russell Gilbert, Graph separator theorems and sparse gaussian elimination, Stanford University, Stanford, CA, 1981
• 21: Gilbert, J. R. 1988. An efficinet parallel sparse partial pivoting algorithm. Tech. Rep. 88/45052-1, Christian Michelsen Institute, Bergen, Norway.
• 22: Gilbert, J. R., Li, X. S., Ng, E. G., and Peyton, B. W. 2001. Computing row and column counts for sparse QR and LU factorization. BIT Numer. Math. 41, 4, 693--710.
• 23: John R. Gilbert , Cleve Moler , Robert Schreiber, Sparse matrices in matlab: design and implementation, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.333-356, Jan. 1992 [doi>10.1137/0613024]
• 24: Gilbert, J. R. and Ng, E. 1993. Predicting structure in nonsymmetric sparse matrix factorizations. In Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert, and J. W. H. Liu, Eds. Springer-Verlag.
• 25: Gilbert, J. R. and Peierls, T. 1988a. Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Statis. Comput. 9, 862--874.
• 26: Gilbert, J. R. and Peierls, T. 1988b. Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Statis. Comput. 9, 862--874.
• 27: Gilbert, J. R. and Schreiber, R. 1982. Nested dissection with partial pivoting. In Sparse Matrix Symposium 1982: Program and Abstracts. Fairfield Glade, Tennessee, 61.
• 28: Nicholas I. M. Gould , Jennifer A. Scott, A numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.300-325, September 2004 [doi>10.1145/1024074.1024077]
• 29: Anshul Gupta, Improved Symbolic and Numerical Factorization Algorithms for Unsymmetric Sparse Matrices, SIAM Journal on Matrix Analysis and Applications, v.24 n.2, p.529-552, 2002 [doi>10.1137/S089547980139604X]
• 30: Anshul Gupta, Recent advances in direct methods for solving unsymmetric sparse systems of linear equations, ACM Transactions on Mathematical Software (TOMS), v.28 n.3, p.301-324, September 2002 [doi>10.1145/569147.569149]
• 31: Dror Irony , Gil Shklarski , Sivan Toledo, Parallel and fully recursive multifrontal sparse Cholesky, Future Generation Computer Systems, v.20 n.3, p.425-440, April 2004 [doi>10.1016/j.future.2003.07.007]
• 32: Xiaoye S. Li , James W. Demmel, SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.110-140, June 2003 [doi>10.1145/779359.779361]
• 33: Joseph W. H. Liu, The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications, v.11 n.1, p.134-172, January 1990 [doi>10.1137/0611010]
• 34: Joseph W. H. Liu , Esmond G. Ng , Barry W. Peyton, On finding supernodes for sparse matrix computations, SIAM Journal on Matrix Analysis and Applications, v.14 n.1, p.242-252, Jan. 1993 [doi>10.1137/0614019]
• 35: Esmond G. Ng , Barry W. Peyton, Block sparse Cholesky algorithms on advanced uniprocessor computers, SIAM Journal on Scientific Computing, v.14 n.5, p.1034-1056, Sept. 1993 [doi>10.1137/0914063]
• 36: Edward Rothberg , Anoop Gupta, Efficient sparse matrix factorization on high performance workstations—exploiting the memory hierarchy, ACM Transactions on Mathematical Software (TOMS), v.17 n.3, p.313-334, Sept. 1991 [doi>10.1145/114697.116809]
• 37: Rozin, E. and Toledo, S. 2005. Locality of reference in sparse Cholesky methods. Electr. Trans. Numer. Anal. 21, 81--106.
• 38: Supercomputing Technologies Group, MIT Laboratory for Computer Science 2001. Cilk-5.3.2 Reference Manual. Supercomputing Technologies Group, MIT Laboratory for Computer Science, Cambridge, MA. Available online at http://supertech.lcs.mit.edu/cilk.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Algorithm design and analysis

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Gaussian elimination, Unsymmetric, multifrontal