SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems

ABSTRACT

We present the main algorithmic features in the software package SuperLU_DIST, a distributed-memory sparse direct solver for large sets of linear equations. We give in detail our parallelization strategies, with a focus on scalability issues, and demonstrate the software's parallel performance and scalability on current machines. The solver is based on sparse Gaussian elimination, with an innovative static pivoting strategy proposed earlier by the authors. The main advantage of static pivoting over classical partial pivoting is that it permits a priori determination of data structures and communication patterns, which lets us exploit techniques used in parallel sparse Cholesky algorithms to better parallelize both LU decomposition and triangular solution on large-scale distributed machines.

REFERENCES

• 1: Alvarado, F. L., Pothen, A., and Schreiber, R. 1993. Highly parallel sparse triangular solution. In Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert, and J. W. Liu, Eds. Springer-Verlag, New York, NY, 159--190.
• 2: Patrick R. Amestoy , Timothy A. Davis , Iain S. Duff, An Approximate Minimum Degree Ordering Algorithm, SIAM Journal on Matrix Analysis and Applications, v.17 n.4, p.886-905, Oct. 1996 [doi>10.1137/S0895479894278952]
• 3: Amestoy, P. R. and Duff, I. S. 1993. Memory management issues in sparse multifrontal methods on multiprocessors. Internat. J. Supercomput. Appl. 7, 1 (Spring), 64--82.
• 4: Patrick R. Amestoy , Iain S. Duff , Jean-Yves L'Excellent , Jacko Koster, A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling, SIAM Journal on Matrix Analysis and Applications, v.23 n.1, p.15-41, 2001 [doi>10.1137/S0895479899358194]
• 5: Patrick R. Amestoy , Iain S. Duff , Jean-Yves L'excellent , Xiaoye S. Li, Analysis and comparison of two general sparse solvers for distributed memory computers, ACM Transactions on Mathematical Software (TOMS), v.27 n.4, p.388-421, December 2001 [doi>10.1145/504210.504212]
• 6: Amestoy, P. R., Li, X. S., and Ng, E. G. 2003. Diagonal markowitz scheme with local symmetrization. Tech. rep., Lawrence Berkeley National Laboratory. In preparatioon.
• 7: 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]
• 8: Arioli, M., Demmel, J. W., and Duff, I. S. 1989. Solving sparse linear systems with sparse backward error. SIAM J. Matrix Anal. Appl. 10, 2 (April), 165--190.
• 9: Ashcraft, C. and Grimes, R. G. 1999. SPOOLES: An object oriented sparse matrix library. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing. (San Antonio, TX. Available online at http://www.netlib.org/linalg/spooles.)
• 10: Cleve Ashcraft , Joseph W. H. Liu, Robust Ordering of Sparse Matrices using Multisection, SIAM Journal on Matrix Analysis and Applications, v.19 n.3, p.816-832, July 1998 [doi>10.1137/S0895479896299081]
• 11: Mark Baertschy , Xiaoye Li, Solution of a three-body problem in quantum mechanics using sparse linear algebra on parallel computers, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.47-47, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582081]
• 12: Michele Benzi , John C. Haws , Miroslav Tuma, Preconditioning Highly Indefinite and Nonsymmetric Matrices, SIAM Journal on Scientific Computing, v.22 n.4, p.1333-1353, 2000 [doi>10.1137/S1064827599361308]
• 13: Jack J. Dongarra , L. S. Blackford , J. Choi , A. Cleary , E. D'Azeuedo , J. Demmel , I. Dhillon , S. Hammarling , G. Henry , A. Petitet , K. Stanley , D. Walker , R. C. Whaley, ScaLAPACK user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 14: Tzu-Yi Chen , James W. Demmel, Preconditioning sparse matrices for computing eigenvalues and solving linear systems of equations, 2001
• 15: Davis, T. A. n.d. University of Florida sparse matrix collection. Available online at http://www.cise.ufl.edu/∼davis/sparse.
• 16: 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]
• 17: Davis, T. A., Gilbert, J. R., Larimore, S. I., and Ng, E. 2000. A column approximate minimum degree ordering algorithm. Tech. Rep. TR-00-005, Computer and Information Sciences Department, University of Florida, Gainesville, FL. Submitted to ACM Trans. Math. Software.
• 18: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 19: 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]
• 20: 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]
• 21: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 22: Duff, I., Grimes, R., and Lewis, J. 1992. Users' guide for the Harwell-Boeing sparse matrix collection (release 1). Tech. Rep. RAL-92-086, Rutherford Appleton Laboratory, Chilton, Didcot, Oxfordshire, U.K.
• 23: Iain S. Duff , Jacko Koster, The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.889-901, Oct. 1999 [doi>10.1137/S0895479897317661]
• 24: Cong Fu , Xiangmin Jiao , Tao Yang, Efficient Sparse LU Factorization with Partial Pivoting on Distributed Memory Architectures, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.109-125, February 1998 [doi>10.1109/71.663864]
• 25: George, A. 1973. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10, 345--363.
• 26: Alan George , Joseph Liu , Esmond Ng, A data structure for sparse QR and LU factorizations, SIAM Journal on Scientific and Statistical Computing, v.9 n.1, p.100-121, January 1988 [doi>10.1137/0909008]
• 27: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 28: 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]
• 29: John R. Gilbert, Predicting Structure in Sparse Matrix Computations, SIAM Journal on Matrix Analysis and Applications, v.15 n.1, p.62-79, Jan. 1994 [doi>10.1137/S0895479887139455]
• 30: John R. Gilbert , Joseph W. H. Liu, Elimination structures for unsymmetric sparse LU factors, SIAM Journal on Matrix Analysis and Applications, v.14 n.2, p.334-352, April 1993 [doi>10.1137/0614024]
• 31: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 32: Gupta, A. 2000. WSMP: Watson Sparse Matrix Package. Tech. Rep., IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY. Available online at http://www.cs.umn. edu/∼agupta/wsmp.html.
• 33: Gupta, A. 2001. Improved symbolic and numerical factorization algorithms for unsymmetric sparse matrices. Tech. Rep. RC 22137 (99131), IBM Research Center, Yorktown Heights, NY.
• 34: Anshul Gupta , George Karypis , Vipin Kumar, Highly Scalable Parallel Algorithms for Sparse Matrix Factorization, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.502-520, May 1997 [doi>10.1109/71.598277]
• 35: Gupta, A. and Kumar, V. 1995. Optimally scalable parallel sparse cholesky factorization. In The 7th SIAM Conference on Parallel Processing for Sci. Comput. 442--447.
• 36: Heath, M. T. and Raghavan, P. 1997. Performance of a fully parallel sparse solver. Internat. J. Supercomput. Appl. 11, 1, 49--64.
• 37: Hendrickson, B. and Leland, R. 1993. The CHACO User's Guide. Version 1.0. Tech. Rep. SAND93-2339 • UC-405, Sandia National Laboratories, Albuquerque, NM.
• 38: Pascal Hénon , Pierre Ramet , Jean Roman, A Mapping and Scheduling Algorithm for Parallel Sparse Fan-In Numerical Factorization, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.1059-1067, August 31-September 03, 1999
• 39: HSL. 2000. A collection of Fortran codes for large scale scientific computation. Available online at http://www.cse.clrc.ac.uk/Activity/HSL.
• 40: Mark T. Jones , Paul E. Plassmann, Scalable iterative solution of sparse linear systems, Parallel Computing, v.20 n.5, p.753-773, May 1994 [doi>10.1016/0167-8191(94)90004-3]
• 41: Karypis, G. and Kumar, V. 1998. MeTiS---A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices---Version 4.0. University of Minnesota, Minneapolis, MN.
• 42: Vipin Kumar , Ananth Grama , Anshul Gupta , George Karypis, Introduction to parallel computing: design and analysis of algorithms, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 43: Lehoucq, R., Maschhoff, K., Sorensen, D., and Yang, C. n.d. Parallel ARPACK. Available online at http://www.caam.rice.edu/∼kristyn/parpack_home.html.
• 44: Xiaoye S. Li , James W. Demmel, Making sparse Gaussian elimination scalable by static pivoting, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-17, November 07-13, 1998, San Jose, CA
• 45: Li, X. S. and Demmel, J. W. 2002. SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems. Tech. Rep. LBNL-49388, Lawrence Berkeley National Laboratory, Berkeley, CA.
• 46: Xiaoye S. Li , James W. Demmel , David H. Bailey , Greg Henry , Yozo Hida , Jimmy Iskandar , William Kahan , Suh Y. Kang , Anil Kapur , Michael C. Martin , Brandon J. Thompson , Teresa Tung , Daniel J. Yoo, Design, implementation and testing of extended and mixed precision BLAS, ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.152-205, June 2002 [doi>10.1145/567806.567808]
• 47: Joseph W. H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Transactions on Mathematical Software (TOMS), v.11 n.2, p.141-153, June 1985 [doi>10.1145/214392.214398]
• 48: 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]
• 49: Markowitz, H. M. 1957. The elimination form of the inverse and its application to linear programming. Management Sci. 3, 255--269.
• 50: MPI. n.d. Message Passing Interface (MPI) forum. Available online at http://www.mpi-forum.org/.
• 51: Olshowka, M. and Neumaier, A. 1996. A new pivoting strategy for Gaussian elimination. Linear Algebra Appl. 240, 131--151.
• 52: Raghavan, P. 1995. Efficient parallel sparse triangular solution with selective inversion. Tech. Rep. CS-95-314, Department of Computer Science, University of Tennessee, Knoxville, TN.
• 53: Rescigno, T. N., Baertschy, M., Isaacs, W. A., and McCurdy, C. W. 1999. Collisional breakup in a quantum system of three charged particles. Science 286, 5449, 2474--2479.
• 54: Riedy, J. 2003. Parallel bipartite matching for sparse matrix computation. In preparation.
• 55: Edward Rothberg, Performance of Panel and Block Approaches to Sparse Cholesky Factorization on the iPSC/860 and Paragon Multicomputers, SIAM Journal on Scientific Computing, v.17 n.3, p.699-713, May 1996 [doi>10.1137/S106482759426715X]
• 56: Saad, Y. n.d. SPARSKIT: A basic tool-kit for sparse matrix computations (Version 2). University of Minnesota, Minneapolis, MN. Available online at http://www.cs.umn.edu/Research/arpa/SPARSKIT/sparskit.html.
• 57: Youcef Saad , Martin H Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.856-869, July 1986 [doi>10.1137/0907058]
• 58: Schenk, O., Gärtner, K., and Fichtner, W. 2000. Efficient sparse LU factorization with left--right looking strategy on shared memory multiprocessors. BIT 40, 1, 158--176.

INDEX TERMS

Primary 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)

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

General Terms:
Algorithms, Performance

Keywords:
Sparse direct solver, distributed-memory computers, parallelism, scalability, supernodal factorization