research-article

Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate

Authors:

Timothy A. Davis,

William W. Hager,

Sivasankaran RajamanickamAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 35, Issue 3

Article No.: 22, Pages 1 - 14

https://doi.org/10.1145/1391989.1391995

Published: 01 October 2008 Publication History

Abstract

CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AA^T, 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 MATLAB^TM 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.

Supplementary Material

Zip (887.zip)

Software for CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate

Download
1.98 MB

References

[1]

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.

Digital Library

[2]

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.

Digital Library

[3]

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.

[4]

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).

Digital Library

[5]

Davis, T. A. 1994. University of Florida sparse matrix collection. www.cise.ufl.edu/research/sparse. NA Digest, vol 92, no. 42.

[6]

Davis, T. A. 2005. Algorithm 849: A concise sparse Cholesky factorization package. ACM Trans. Math. Softw. 31, 4, 587--591.

Digital Library

[7]

Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. SIAM, Philadelphia, PA.

Digital Library

[8]

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.

Digital Library

[9]

Davis, T. A. and Hager, W. W. 1999. Modifying a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 20, 3, 606--627.

Digital Library

[10]

Davis, T. A. and Hager, W. W. 2001. Multiple-rank modifications of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 22, 997--1013.

Digital Library

[11]

Davis, T. A. and Hager, W. W. 2007a. Dual multilevel optimization. Math. Program. 112, 2 (Nov.), 403--425.

Digital Library

[12]

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.

Digital Library

[13]

Davis, T. A. and Hager, W. W. 2009. Dynamic supernodes in sparse Cholesky update/downdate and triangular solves. ACM Trans. Math. Softw., to appear.

Digital Library

[14]

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.

[15]

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.

Digital Library

[16]

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.

Digital Library

[17]

Duff, I. S., Erisman, A. M., and Reid, J. K. 1986. Direct Methods for Sparse Matrices. OUP, Oxford, UK.

Digital Library

[18]

George, A. and Liu, J. W. H. 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs, New Jersey.

Digital Library

[19]

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.

Digital Library

[20]

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.

Digital Library

[21]

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.

Digital Library

[22]

Gill, P. E., Golub, G. H., Murray, W., and Saunders, M. A. 1974. Methods for modifying matrix factorizations. Math. Comp. 28, 126, 505--535.

[23]

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.

[24]

Goto, K. and van de Geijn, R. 2008. High performance implementation of the level-3 BLAS. ACM Trans. Math. Softw. 35, 1.

Digital Library

[25]

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.)

[26]

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.

Digital Library

[27]

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.

[28]

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.

Digital Library

[29]

Hager, W. W. 1989. Updating the inverse of a matrix. SIAM Rev. 31, 2, 221--239.

Digital Library

[30]

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.

Digital Library

[31]

Karypis, G. and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359--392.

Digital Library

[32]

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.

Digital Library

[33]

Liu, J. W. H. 1985. Modification of the minimum-degree algorithm by multiple elimination. ACM Trans. Math. Softw. 11, 2, 141--153.

Digital Library

[34]

Liu, J. W. H. 1990. The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11, 1, 134--172.

Digital Library

[35]

Moler, C. June 2007. Cleve’s corner: parallel MATLAB: multiple processors and multiple cores. MATLAB News and Notes.

[36]

Ng, E. G. and Peyton, B. W. 1993. Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM J. Sci. Comput. 14, 5, 1034--1056.

Digital Library

[37]

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.

[38]

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.

Digital Library

[39]

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.

Digital Library

[40]

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.

Digital Library

[41]

Scott, J. A. and Hu, Y. 2007. Experiences of sparse direct symmetric solvers. ACM Trans. Math. Softw. 33, 3.

Digital Library

[42]

Stewart, G. W. 1979. The effects of rounding error on an algorithm for downdating a Cholesky factorization. J. Inst. Math. Appl. 23, 203--213.

[43]

Stewart, G. W. 1998. Matrix algorithms, Volume 1: Basic decompositions. SIAM, Philadelphia.

Cited By

Heroux MClaus LGhysels PBoukaram WLi X(2025)A graphics processing unit accelerated sparse direct solver and preconditioner with block low rank compressionInternational Journal of High Performance Computing Applications10.1177/1094342024128856739:1(18-31)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1177/10943420241288567
Abdelkarim AVoos HGörges D(2025)Factor Graphs in Optimization-Based Robotic Control—A Tutorial and ReviewIEEE Access10.1109/ACCESS.2025.353499313(28315-28334)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3534993
Alberdi RHamel CTalamini BTupek M(2025)An optimization-based approach to tailor the mechanical response of soft metamaterials undergoing rate-dependent instabilitiesComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2024.117679435(117679)Online publication date: Feb-2025
https://doi.org/10.1016/j.cma.2024.117679
Show More Cited By

Index Terms

Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
  2. Mathematical software

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 35, Issue 3

October 2008

164 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1391989

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2008

Accepted: 01 March 2008

Revised: 01 March 2008

Received: 01 September 2006

Published in TOMS Volume 35, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

566
Total Citations
View Citations
2,834
Total Downloads

Downloads (Last 12 months)156
Downloads (Last 6 weeks)17

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Heroux MClaus LGhysels PBoukaram WLi X(2025)A graphics processing unit accelerated sparse direct solver and preconditioner with block low rank compressionInternational Journal of High Performance Computing Applications10.1177/1094342024128856739:1(18-31)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1177/10943420241288567
Abdelkarim AVoos HGörges D(2025)Factor Graphs in Optimization-Based Robotic Control—A Tutorial and ReviewIEEE Access10.1109/ACCESS.2025.353499313(28315-28334)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3534993
Alberdi RHamel CTalamini BTupek M(2025)An optimization-based approach to tailor the mechanical response of soft metamaterials undergoing rate-dependent instabilitiesComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2024.117679435(117679)Online publication date: Feb-2025
https://doi.org/10.1016/j.cma.2024.117679
Anderka RDeisenroth MTakao SKiyavash NMooij J(2024)Iterated INLA for state and parameter estimation in nonlinear dynamical systemsProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702678(50-76)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.5555/3702676.3702678
Lan KGueidon EKaneda APanetta JTeran JSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)A neural-preconditioned poisson solver for mixed Dirichlet and Neumann boundary conditionsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693109(25976-25994)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693109
Anantharamu SCockburn B(2024)Efficient implementation of the hybridized Raviart-Thomas mixed method by converting flux subspaces into stabilizationsMathematics in Engineering10.3934/mine.20240106:2(221-237)Online publication date: 2024
https://doi.org/10.3934/mine.2024010
Fang ZWang H(2024)GPU accelerated sparse curvelet-constrained wavefield reconstruction inversion with source estimation: Application to Chevron Benchmark 2014 blind test data setGEOPHYSICS10.1190/geo2023-0685.189:5(R443-R455)Online publication date: 12-Aug-2024
https://doi.org/10.1190/geo2023-0685.1
Vella CGosselet PPrudhomme S(2024)An efficient PGD solver for structural dynamics applicationsAdvanced Modeling and Simulation in Engineering Sciences10.1186/s40323-024-00269-z11:1Online publication date: 23-Jul-2024
https://doi.org/10.1186/s40323-024-00269-z
Heroux MAbdelfattah ABeams NCarson RGhysels PKolev TStitt TVargas ATomov SDongarra J(2024)MAGMAInternational Journal of High Performance Computing Applications10.1177/1094342024126196038:5(468-490)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1177/10943420241261960
Mejia-Domenzain LChen JLourenco CMoreno-Centeno EDavis T(2024)Algorithm 1050: SPEX Cholesky, LDL, and Backslash for Exactly Solving Sparse Linear SystemsACM Transactions on Mathematical Software10.1145/370059250:4(1-29)Online publication date: 11-Dec-2024
https://dl.acm.org/doi/10.1145/3700592
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents