A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations

ABSTRACT

In recent years a number of solvers for the direct solution of large sparse symmetric linear systems of equations have been developed. These include solvers that are designed for the solution of positive definite systems as well as those that are principally intended for solving indefinite problems. In this study, we use performance profiles as a tool for evaluating and comparing the performance of serial sparse direct solvers on an extensive set of symmetric test problems taken from a range of practical applications.

REFERENCES

• 1: Amestoy, P. 1997. Recent progress in parallel multifrontal solvers for unsymmetric sparse matrices. In Proceedings of the 15th World Congress on Scientific Computation, Modelling and Applied Mathematics, IMACS 97, Berlin.
• 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: Patrick R. Amestoy , Enseeiht-Irit , Timothy A. Davis , Iain S. Duff, Algorithm 837: AMD, an approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.381-388, September 2004 [doi>10.1145/1024074.1024081]
• 4: Amestoy, P., Duff, I., and L'Excellent, J. 2000. Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput. Methods in Appl. Mech. Eng 184, 501--520.
• 5: 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]
• 6: Arioli, M., Demmel, J., and Duff, I. 1989. Solving sparse linear systems with sparse backward error. SIAM J. Matrix Anal. Appl. 10, 165--190.
• 7: 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]
• 8: 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]
• 9: Bunch, J. and Kaufmann, L. 1977. Some stable methods for calculating inertia and solving symmetric linear systmes. Math. Comput. 31, 163--179.
• 10: Bunch, J., Kaufmann, L., and Parlett, B. 1976. Decomposition of a symmetric matrix. Numerische Mathematik 27, 95--110.
• 11: 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]
• 12: 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]
• 13: Davis, T. and Duff, I. 1993. An unsymmetric-pattern multifrontal method for sparse LU factorization. Tech. Rep. RAL-93-036, Rutherford Appleton Laboratory.
• 14: 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]
• 15: 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]
• 16: 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]
• 17: Timothy A. Davis , William W. Hager, Multiple-Rank Modifications of a Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.22 n.4, p.997-1013, 2000 [doi>10.1137/S0895479899357346]
• 18: Timothy A. Davis , William W. Hager, Row Modifications of a Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.26 n.3, p.621-639, 2005 [doi>10.1137/S089547980343641X]
• 19: 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.
• 20: Dolan, E. and Moré, J. 2002. Benchmarking optimization software with performance profiles. Mathematical Programming 91, 2, 201--213.
• 21: 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]
• 22: 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
• 23: 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]
• 24: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 25: I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
• 26: 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]
• 27: Iain S. Duff , Stéphane Pralet, Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems, SIAM Journal on Matrix Analysis and Applications, v.27 n.2, p.313-340, 2005 [doi>10.1137/04061043X]
• 28: Duff, I. and Pralet, S. 2005. Towards a stable static pivoting strategy for the sequential and parallel solution of sparse symmetric indefinite systems. Tech. Rep. RAL-TR-2005-007, Rutherford Appleton Laboratory.
• 29: 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]
• 30: Duff, I. and Scott, J. 2005. Towards an automatic ordering for a symmetric sparse direct solver. Tech. Rep. RAL-TR-2006-001, Rutherford Appleton Laboratory.
• 31: George, A. 1973. Nested dissection of a regular finite-element mesh. SIAM J. Numer. Anal. 10, 345--363.
• 32: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 33: 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]
• 34: 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.
• 35: 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.
• 36: 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]
• 37: Nicholas I. M. Gould , Philippe L. Toint, An iterative working-set method for large-scale nonconvex quadratic programming, Applied Numerical Mathematics, v.43 n.1-2, p.109-128, October 2002 [doi>10.1016/S0168-9274(02)00120-4]
• 38: Gupta, A., Joshi, M., and Kumar, V. 2001. WSMP: A high-performance serial and parallel sparse linear solver. Tech. Rep. RC 22038 (98932), IBM T.J. Watson Reserach Center. www.cs.umn.edu/~agupta/doc/wssmp-paper.ps.
• 39: 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]
• 40: Michael T. Heath , Esmond Ng , Barry W. Peyton, Parallel algorithms for sparse linear systems, SIAM Review, v.33 n.3, p.420-460, Sept. 1991 [doi>10.1137/1033099]
• 41: HSL. 2004. A collection of Fortran codes for large-scale scientific computation. See http://www.cse.clrc.ac.uk/nag/hsl/.
• 42: 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. See http://www-users.cs.umn.edu/~karypis/metis/.
• 43: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 44: 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]
• 45: Joseph W. H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review, v.34 n.1, p.82-109, March 1992 [doi>10.1137/1034004]
• 46: 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]
• 47: 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]
• 48: Saunders, M. 1994. Sparse matrices in optimization. Presented at Sparse Days at St Girons, International meeting on Sparse Matrix Methods, St Girons, France. See http://www.stanford.edu/group/SOL/talks/saunders-stgirons.ps.
• 49: Schenk, O. and Gärtner, K. 2004a. On fast factorization pivoting methods for sparse symmetric indefinite systems. Tech. Rep. CS-2004-004, Department of Computer Science, University of Basel, Switzerland.
• 50: 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]
• 51: 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.
• 52: Schulze, J. 2001. Towards a tighter coupling of bottom-up and top-down sparse matrix ordering methods. BIT 41, 800--841.
• 53: Tinney, W. and Walker, J. 1967. Direct solutions of sparse network equations by optimally ordered triangular factorization. Proc. IEEE 55, 1801--1809.

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:
Gaussian elimination, Sparse matrices, direct solvers, software, symmetric linear systems