Jennifer A. Scott
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.
- Amestoy, P., Duff, I., L'Excellent, J., and Koster, J. 2001. A fully asynchronmous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Applic. 23, 15--41. Google Scholar
- 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.Google Scholar
- Ashcraft, C., Grimes, R., and Lewis, J. 1998. Accurate symmetric indefinite linear equation solvers. SIAM J. Matrix Anal. Applic. 20, 513--561. Google Scholar
- Davis, T. 2003. Algorithm 832: UMFPACK, an unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30, 2, 196--199. Google Scholar
- Davis, T., Hager, W., and Rajamanickam, S. 2006. Algorithm: CHOLMOD, a sparse cholesky factirization and modification package. In preparation. Google Scholar
- 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.Google Scholar
- Dolan, E. and Moré, J. 2002. Benchmarking optimization software with performance profiles. Math. Program. 91, 2, 201--213.Google Scholar
- Dongarra, J., Duff, I., Sorensen, D., and van der Vorst, H. 1998. Numerical Linear Algebra for High-Performance Computers. SIAM. Google Scholar
- Duff, I. 2004. MA57---a new code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30, 118--154. Google Scholar
- Duff, I., Erisman, A., and Reid, J. 1986. Direct Methods for Sparse Matrices. Oxford University Press. Google Scholar
- Duff, I. and Reid, J. 1983. The multifrontal solution of indefinite sparse symmetric linear systems. ACM Trans. Math. Softw. 9, 302--325. Google Scholar
- Duff, I. and Reid, J. 1996. Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric systems. ACM Trans. Math. Softw. 22, 227--257. Google Scholar
- Duff, I. and Scott, J. 1999. A frontal code for the solution of sparse positive-definite symmetric systems arising from finite-element applications. ACM Trans. Math. Softw. 25, 404--424. Google Scholar
- Gilbert, J., Ng, E., and Peyton, B. 1994. An efficient algorithm to compute row and column counts for sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 15, 1075--1091. Google Scholar
- 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.Google Scholar
- Gould, N., Hu, Y., and Scott, J. 2007. A numerical evaluation of sparse solvers for symmetric systems. ACM Trans. Math. Softw. 33, 2, Article 10. Google Scholar
- 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.Google Scholar
- Gould, N. and Scott, J. 2004. A numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations. ACM Trans. Math. Softw. 30, 300--325. Google Scholar
- 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.Google Scholar
- HSL. 2004. A collection of Fortran codes for large-scale scientific computation. See http://www.cse.clrc.ac.uk/nag/hsl/.Google Scholar
- Rotkin, V. and Toledo, S. 2004. The design and implementation of a new out-of-core sparse Cholesky factorization method. ACM Trans. Math. Softw. 30, 19--46. Google Scholar
- Schenk, O. and Gärtner, K. 2004. Solving unsymmetric sparse systems of linear equations with PARDISO. J. Fut. Gener. Comput. Syst. 20, 3, 475--487. Google Scholar
- 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).Google Scholar
Index Terms
- Experiences of sparse direct symmetric solvers
Recommendations
A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations
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 ...
A numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations
In recent years, a number of new direct solvers for the solution of large sparse, symmetric linear systems of equations have been added to the mathematical software library HSL. These include solvers that are designed for the solution of positive-...
The State-of-the-Art of Preconditioners for Sparse Linear Least-Squares Problems
In recent years, a variety of preconditioners have been proposed for use in solving large sparse linear least-squares problems. These include simple diagonal preconditioning, preconditioners based on incomplete factorizations, and stationary inner ...
Reviews
Kai Diethelm
In a recent paper [1], the authors (together with Gould) carried out extensive numerical experiments with a large number of algorithms, for the direct solution of sparse symmetric linear systems. The results of the experiments, in terms of the performance of the tested algorithms, are reported in that paper. "Experiences of sparse direct symmetric solvers" is a very useful byproduct of those investigations. Specifically, the authors describe the experience that was gained from running the tests; the quality of the documentations is of course an important aspect. Other issues of interest are the details of the license, and the difficulties with obtaining the code and possible updates. When it comes to actually using the software, it is necessary to look at the interfaces and calling sequences of the subroutines: Are they user friendly__?__ Do they provide an opportunity to exercise some influence over the parameters of the algorithm, if the user wants to do so__?__ Will the code provide useful default values for the parameters, if the user does not have any information on how to set the parameters__?__ How does the code handle errors and exceptions__?__ The discussion of these aspects gives the user helpful hints when it comes to the selection of a particular algorithm, and also gives the software developer some guidelines to follow when preparing the code for publication. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments