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 ScholarDigital 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
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 ...
Algorithm 849: A concise sparse Cholesky factorization package
The LDL software package is a set of short, concise routines for factorizing symmetric positive-definite sparse matrices, with some applicability to symmetric indefinite matrices. Its primary purpose is to illustrate much of the basic theory of sparse ...
Comments