research-article

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

Authors:

Yanqing Chen,

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

Get Access

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

Google Scholar

[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

Google Scholar

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

Google Scholar

[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

Google Scholar

[5]

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

Google Scholar

[6]

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

Digital Library

Google Scholar

[7]

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

Digital Library

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[11]

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

Digital Library

Google Scholar

[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

Google Scholar

[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

Google Scholar

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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[17]

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

Digital Library

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

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

Google Scholar

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

Crossref

Google Scholar

[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

Google Scholar

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

Google Scholar

[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

Google Scholar

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

Google Scholar

[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

Google Scholar

[29]

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

Digital Library

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[35]

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

Google Scholar

[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

Google Scholar

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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[41]

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

Digital Library

Google Scholar

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

Crossref

Google Scholar

[43]

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

Google Scholar

Cited By

View all

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

Reviews

Reviewer: 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

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

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

552
Total Citations
View Citations
2,799
Total Downloads

Downloads (Last 12 months)159
Downloads (Last 6 weeks)19

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Jiang YSong JYin XDong XSun SLin YJin ZYang XZhuo CAmrouch HHu JGarg SLin Y(2024)A Parallel Simulation Framework Incorporating Machine Learning-Based Hotspot Detection for Accelerated Power Grid AnalysisProceedings of the 2024 ACM/IEEE International Symposium on Machine Learning for CAD10.1145/3670474.3685947(1-7)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3670474.3685947
Numerow LLi YCoros SThomaszewski B(2024)Differentiable Voronoi Diagrams for Simulation of Cell-Based Mechanical SystemsACM Transactions on Graphics10.1145/365815243:4(1-11)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658152
Li YNumerow LThomaszewski BCoros S(2024)Differentiable Geodesic Distance for Intrinsic Minimization on Triangle MeshesACM Transactions on Graphics10.1145/365812243:4(1-14)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658122
Eftekhari AGaedke-Merzhäuser LPasadakis DBollhöfer MScheidegger SSchenk O(2024)Algorithm 1042: Sparse Precision Matrix Estimation with SQUICACM Transactions on Mathematical Software10.1145/365010850:2(1-18)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1145/3650108
Liu ZYu WDe V(2024)PowerRChol: Efficient Power Grid Analysis Based on Fast Randomized Cholesky FactorizationProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3657308(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3657308
Lin SYang WHu YCai QDai MWang HLi K(2024)HPS Cholesky: Hierarchical Parallelized Supernodal Cholesky with Adaptive ParametersACM Transactions on Parallel Computing10.1145/363005111:1(1-22)Online publication date: 11-Mar-2024
https://dl.acm.org/doi/10.1145/3630051
Show More Cited By

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm

Dynamic Supernodes in Sparse Cholesky Update/Downdate and Triangular Solves

Algorithm 832: UMFPACK V4.3---an unsymmetric-pattern multifrontal method

Reviews

Access critical reviews of Computing literature here