Yanqing Chen
Timothy A. Davis
William W. Hager
Abstract
CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AAT, updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, and many other sparse matrix functions for both symmetric and unsymmetric matrices. Its supernodal Cholesky factorization relies on LAPACK and the Level-3 BLAS, and obtains a substantial fraction of the peak performance of the BLAS. Both real and complex matrices are supported. CHOLMOD is written in ANSI/ISO C, with both C and MATLABTM interfaces. It appears in MATLAB 7.2 as x = A\b when A is sparse symmetric positive definite, as well as in several other sparse matrix functions.
Supplemental Material
Available for Download
Software for CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate
- Amestoy, P. R., Davis, T. A., and Duff, I. S. 1996. An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17, 4, 886--905. Google Scholar
Digital Library
- Anderson, E., Bai, Z., Bischof, C. H., Blackford, S., Demmel, J. W., Dongarra, J. J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., and Sorensen, D. C. 1999. LAPACK Users’ Guide, 3rd ed. SIAM, Philadelphia. Google ScholarDigital Library
- Ashcraft, C. 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. SIAM, Philadelphia.Google Scholar
- Boisvert, R. F., Pozo, R., Remington, K., Barrett, R., and Dongarra, J. J. 1997. The Matrix Market: A Web resource for test matrix collections. In Quality of Numerical Software, Assessment and Enhancement, R. F. Boisvert, Ed. Chapman & Hall, London, 125--137. (http://math.nist.gov/MatrixMarket). Google ScholarDigital Library
- Davis, T. A. 1994. University of Florida sparse matrix collection. www.cise.ufl.edu/research/sparse. NA Digest, vol 92, no. 42.Google Scholar
- Davis, T. A. 2005. Algorithm 849: A concise sparse Cholesky factorization package. ACM Trans. Math. Softw. 31, 4, 587--591. Google ScholarDigital Library
- Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Davis, T. A., Gilbert, J. R., Larimore, S. I., and Ng, E. G. 2004. A column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 3, 353--376. Google ScholarDigital Library
- Davis, T. A. and Hager, W. W. 1999. Modifying a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 20, 3, 606--627. Google ScholarDigital Library
- Davis, T. A. and Hager, W. W. 2001. Multiple-rank modifications of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 22, 997--1013. Google ScholarDigital Library
- Davis, T. A. and Hager, W. W. 2007a. Dual multilevel optimization. Math. Program. 112, 2 (Nov.), 403--425. Google ScholarDigital Library
- Davis, T. A. and Hager, W. W. 2007b. A sparse proximal implementation of the LP Dual Active Set Algorithm. Math. Program. 112, 2 (Nov.), 275--301. Google ScholarDigital Library
- Davis, T. A. and Hager, W. W. 2009. Dynamic supernodes in sparse Cholesky update/downdate and triangular solves. ACM Trans. Math. Softw., to appear. Google ScholarDigital Library
- Dobrian, F., Kumfert, G. K., and Pothen, A. 2000. The design of sparse direct solvers using object oriented techniques. In Advances in Software Tools for Scientific Computing, H. P. Langtangen, A. M. Bruaset, and E. Quak, Eds. Lecture Notes in Computational Science and Engineering, vol. 10. Springer-Verlag, Berlin, 89--131.Google Scholar
- Dongarra, J. J., Du Croz, J., Duff, I. S., and Hammarling, S. 1990. A set of level-3 basic linear algebra subprograms. ACM Trans. Math. Softw. 16, 1, 1--17. Google ScholarDigital Library
- Dongarra, J. J., Du Croz, J., Hammarling, S., and Hanson, R. J. 1988. An extended set of Fortran basic linear algebra subprograms. ACM Trans. Math. Softw. 14, 18--32. Google ScholarDigital Library
- Duff, I. S., Erisman, A. M., and Reid, J. K. 1986. Direct Methods for Sparse Matrices. OUP, Oxford, UK. Google ScholarDigital Library
- George, A. and Liu, J. W. H. 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs, New Jersey. Google ScholarDigital Library
- 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 41, 4, 693--710.Google ScholarDigital Library
- Gilbert, J. R., Moler, C., and Schreiber, R. 1992. Sparse matrices in MATLAB: design and implementation. SIAM J. Matrix Anal. Appl. 13, 1, 333--356. Google ScholarDigital Library
- Gilbert, J. R., Ng, E. G., and Peyton, B. W. 1994. An efficient algorithm to compute row and column counts for sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 15, 4, 1075--1091. Google ScholarDigital Library
- Gill, P. E., Golub, G. H., Murray, W., and Saunders, M. A. 1974. Methods for modifying matrix factorizations. Math. Comp. 28, 126, 505--535.Google Scholar
- Gochman, S., Mendelson, A., Naveh, A., and Rotem, E. 2006. Introduction to the Intel core duo processor architecture. Intel Techn. J. 10, 2, 89--98.Google ScholarCross Ref
- Goto, K. and van de Geijn, R. 2008. High performance implementation of the level-3 BLAS. ACM Trans. Math. Softw. 35, 1. Google ScholarDigital Library
- Gould, N. I. M., Hu, Y., and Scott, J. A. 2006. Complete results from a numerical evaluation of sparse direct solvers for the solution of large sparse, symmetric linear systems of equations. Tech. Rep. Internal report 2005-1 (revision 2), CCLRC, Rutherford Appleton Laboratory. (Mar.)Google Scholar
- Gould, N. I. M., Hu, Y., and Scott, J. A. 2007. A numerical evaluation of sparse direct solvers for the solution of large sparse, symmetric linear systems of equations. ACM Trans. Math. Softw. 33, 2 (June), 32 pages. Google ScholarDigital Library
- 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 Research Center.Google Scholar
- Gupta, A., Karypis, G., and Kumar, V. 1997. Highly scalable parallel algorithms for sparse matrix factorization. IEEE Trans. Para. Distrib. Syst. 8, 5, 502--520. Google ScholarDigital Library
- Hager, W. W. 1989. Updating the inverse of a matrix. SIAM Rev. 31, 2, 221--239. Google ScholarDigital Library
- Hénon, P., Ramet, P., and Roman, J. 2002. PaStiX: A high-performance parallel direct solver for sparse symmetric definite systems. Para. Comput. 28, 2, 301--321. Google ScholarDigital Library
- Karypis, G. and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359--392. Google ScholarDigital Library
- Lawson, C. L., Hanson, R. J., Kincaid, D. R., and Krogh, F. T. 1979. Basic linear algebra subprograms for Fortran usage. ACM Trans. Math. Softw. 5, 308--323. Google ScholarDigital Library
- Liu, J. W. H. 1985. Modification of the minimum-degree algorithm by multiple elimination. ACM Trans. Math. Softw. 11, 2, 141--153. Google ScholarDigital Library
- Liu, J. W. H. 1990. The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11, 1, 134--172. Google ScholarDigital Library
- Moler, C. June 2007. Cleve’s corner: parallel MATLAB: multiple processors and multiple cores. MATLAB News and Notes.Google Scholar
- Ng, E. G. and Peyton, B. W. 1993. Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM J. Sci. Comput. 14, 5, 1034--1056. Google ScholarDigital Library
- Pellegrini, F., Roman, J., and Amestoy, P. R. 2000. Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering. Concurrency: Pract. Exp. 12, 68--84.Google Scholar
- Rothberg, E. and Eisenstat, S. C. 1998. Node selection strategies for bottom-up sparse matrix orderings. SIAM J. Matrix Anal. Appl. 19, 3, 682--695. Google ScholarDigital Library
- Rothberg, E. and Gupta, A. 1991. Efficient sparse matrix factorization on high-performance workstations---exploiting the memory hierarchy. ACM Trans. Math. Softw. 17, 3, 313--334. Google ScholarDigital Library
- 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, 1, 19--46. Google ScholarDigital Library
- Scott, J. A. and Hu, Y. 2007. Experiences of sparse direct symmetric solvers. ACM Trans. Math. Softw. 33, 3. Google ScholarDigital Library
- Stewart, G. W. 1979. The effects of rounding error on an algorithm for downdating a Cholesky factorization. J. Inst. Math. Appl. 23, 203--213.Google ScholarCross Ref
- Stewart, G. W. 1998. Matrix algorithms, Volume 1: Basic decompositions. SIAM, Philadelphia.Google Scholar
Index Terms
- Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate
Recommendations
Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm
Two codes are discussed, COLAMD and SYMAMD, that compute approximate minimum degree orderings for sparse matrices in two contexts: (1) sparse partial pivoting, which requires a sparsity preserving column pre-ordering prior to numerical factorization, ...
Dynamic Supernodes in Sparse Cholesky Update/Downdate and Triangular Solves
The supernodal method for sparse Cholesky factorization represents the factor L as a set of supernodes, each consisting of a contiguous set of columns of L with identical nonzero pattern. A conventional supernode is stored as a dense submatrix. While ...
Algorithm 832: UMFPACK V4.3---an unsymmetric-pattern multifrontal method
An ANSI C code for sparse LU factorization is presented that combines a column pre-ordering strategy with a right-looking unsymmetric-pattern multifrontal numerical factorization. The pre-ordering and symbolic analysis phase computes an upper bound on ...
Reviews
Kai Diethelm
The solution of large sparse positive definite linear systems of equations is a problem frequently encountered in many applications in scientific computing. The dimension of typical problems has grown substantially over the recent years and there is no reason to believe that we have reached the end of this growth. Therefore, there is a substantial demand for fast and reliable algorithms to solve such equations. Many modern algorithms in this context are based on Cholesky decompositions. This paper describes CHOLMOD, a package of subroutines built for handling such decompositions, the required preprocessing and postprocessing, and related issues. CHOLMOD contains 134 user-callable routines that cover all potential problems that one can encounter in such a context. Moreover, the routines give the user a great deal of opportunity to choose the specific version of the algorithm that best suits the concrete application at hand. A particularly important question in this respect is the ordering strategy for the algorithm. A poor choice here may lead to a highly inefficient and slow procedure. Therefore, a very useful feature that CHOLMOD offers is not only various possible ordering methods?including (approximate) minimum degree ordering, nested dissection, and METIS?but also some tools for the user that allow him or her to find a good method. The description of the package is very detailed and complete. The numerical examples provided indicate that it performs very well. It should be a very useful tool for anyone who needs to deal with large sparse positive definite systems?an observation confirmed by the fact that CHOLMOD has been integrated into MATLAB. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments