Experiences of sparse direct symmetric solvers

ABSTRACT

We recently carried out an extensive comparison of the performance of state-of-the-art sparse direct solvers for the numerical solution of symmetric linear systems of equations. Some of these solvers were written primarily as research codes while others have been developed for commercial use. Our experiences of using the different packages to solve a wide range of problems arising from real applications were mixed. In this paper, we highlight some of these experiences with the aim of providing advice to both software developers and users of sparse direct solvers. We discuss key features that a direct solver should offer and conclude that while performance is an essential factor to consider when choosing a code, there are other features that a user should also consider looking for that vary significantly between packages.

REFERENCES

• 1: 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]
• 2: Ashcraft, C. and Grimes, R. 1999. SPOOLES: An object-oriented sparse matrix library. In Proceedings of the 9th SIAM Conference on Parallel Processing. Software available at http://www.netlib.org/linalg/spooles.
• 3: Cleve Ashcraft , Roger G. Grimes , John G. Lewis, Accurate Symmetric Indefinite Linear Equation Solvers, SIAM Journal on Matrix Analysis and Applications, v.20 n.2, p.513-561, April 1999 [doi>10.1137/S0895479896296921]
• 4: Timothy A. Davis, Algorithm 832: UMFPACK V4.3---an unsymmetric-pattern multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.196-199, June 2004 [doi>10.1145/992200.992206]
• 5: Timothy A. Davis , William W. Hager, Modifying a Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.606-627, July 1999 [doi>10.1137/S0895479897321076]
• 6: Dobrian, F., Kumfert, G., and Pothen, A. 2000. The design of sparse direct solvers using object-oriented techniques. In Advances in Software Tools in Scientific Computing, H. Langtangen, A. Bruaset, and E. Quak, Eds. Lecture Notes in Computational Science and Engineering, vol. 50. Springer-Verlag, 89--131.
• 7: Dolan, E. and Moré, J. 2002. Benchmarking optimization software with performance profiles. Math. Program. 91, 2, 201--213.
• 8: Jack J. Dongarra , Lain S. Duff , Danny C. Sorensen , Henk A. Vander Vorst, Numerical Linear Algebra for High Performance Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 9: Iain S. Duff, MA57---a code for the solution of sparse symmetric definite and indefinite systems, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.118-144, June 2004 [doi>10.1145/992200.992202]
• 10: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 11: 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]
• 12: I. S. Duff , J. K. Reid, Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.227-257, June 1996 [doi>10.1145/229473.229480]
• 13: Iain S. Duff , Jennifer A. Scott, A frontal code for the solution of sparse positive-definite symmetric systems arising from finite-element applications, ACM Transactions on Mathematical Software (TOMS), v.25 n.4, p.404-424, Dec. 1999 [doi>10.1145/332242.332243]
• 14: John R. Gilbert , Esmond G. Ng , Barry W. Peyton, An Efficient Algorithm to Compute Row and Column Counts for Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.15 n.4, p.1075-1091, Oct. 1994 [doi>10.1137/S0895479892236921]
• 15: Gould, N., Hu, Y., and Scott, J. 2005. Complete results for a numerical evaluation of sparse direct solvers for the solution of large, sparse, symmetric linear systems of equations. Numerical Analysis Internal Report 2005-1, Rutherford Appleton Laboratory. Available from www.numerical.rl.ac.uk/reports/reports.shtml.
• 16: Nicholas I. M. Gould , Jennifer A. Scott , Yifan Hu, A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.33 n.2, p.10-es, June 2007 [doi>10.1145/1236463.1236465]
• 17: Gould, N. and Scott, J. 2003. Complete results for a numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations. Numerical Analysis Internal Report 2003-2, Rutherford Appleton Laboratory. Available from www.numerical.rl.ac.uk/reports/reports.shtml.
• 18: 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]
• 19: Gupta, A. 2000. WSMP Watson sparse matrix package (Part II: direct solution of general sparse systems. Tech. rep. RC 21888 (98472), IBM T.J. Watson Reserach Center. www.cs.umn.edu/~agupta/wsmp.html.
• 20: HSL. 2004. A collection of Fortran codes for large-scale scientific computation. See http://www.cse.clrc.ac.uk/nag/hsl/.
• 21: Vladimir Rotkin , Sivan Toledo, The design and implementation of a new out-of-core sparse cholesky factorization method, ACM Transactions on Mathematical Software (TOMS), v.30 n.1, p.19-46, March 2004 [doi>10.1145/974781.974783]
• 22: Olaf Schenk , Klaus Gärtner, Solving unsymmetric sparse systems of linear equations with PARDISO, Future Generation Computer Systems, v.20 n.3, p.475-487, April 2004 [doi>10.1016/j.future.2003.07.011]
• 23: Whaley, R., Petitet, A., and Dongarra, J. 2001. Automated empirical optimization of software and the ATLAS project. Parall. Comput. 27, 1--2, 3--35. Also available as University of Tennessee LAPACK Working Note #147, UT-CS-00-448, 2000 (www.netlib.org/lapack/lawns/lawn147.ps).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

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)

Keywords:
Sparse matrices, direct solvers, software development, symmetric linear systems