CHOLMOD:

CHOLMOD is a set of ANSI C routines for sparse Cholesky factorization and update/downdate. A MATLAB interface is provided.

Single-threaded performance:

The performance of CHOLMOD was compared with 10 other codes in a paper by Nick Gould, Yifan Hu, and Jennifer Scott. see also their raw data. Comparing BCSLIB-EXT, CHOLMOD, MA57, MUMPS, Oblio, PARDISO, SPOOLES, SPRSBLKLLT, TAUCS, UMFPACK, and WSMP, on 87 large symmetric positive definite matrices, they found CHOLMOD to be fastest for 42 of the 87 matrices. Its run time is either fastest or within 10% of the fastest for 73 out of 87 matrices. Considering just the larger matrices, it is either the fastest or within 10% of the fastest for 40 out of 42 matrices. It uses the least amount of memory (or within 10% of the least) for 35 of the 42 larger matrices. Jennifer Scott and Yifan Hu also discuss the design considerations for a sparse direct code.

Click here for a comparison of CHOLMOD with the preconditioned conjugate gradients method.

Muli-threaded performance and Cleve's Corner:

CHOLMOD appears in MATLAB as chol, etree, symbfact, and backslash when A is sparse and symmetric positive definite. It was highlighted in the June 2007 Cleve's Corner article by Cleve Moler, who found that CHOLMOD is slower when multithreading is enabled. The problem is not CHOLMOD. The current Intel, AMD, Sun, and even Goto BLAS are all horribly slow when multithreading is enabled, for the kinds of calls that CHOLMOD makes to the BLAS. Click here for more details on the BLAS. CHOLMOD uses mostly transposed BLAS calls (C=A*B' in dgemm, C=A*A' in dsyrk, and X=B/L' in dtrsm). For dtrsm, the side='R' option is the culprit (for Intel and Sun, but not AMD). For dgemm, the problem is made worse because the matrices tend to be tall and thin. These kernels are not intrinsically slow, but all BLAS authors have ignored their performance when creating multithreaded versions. With multithreading enabled, the performance of CHOLMOD, and the MATLAB sparse bench, will be slow until the BLAS authors fix the performance bug. In the meantime, if you do a lot of sparse matrix work in MATLAB, be sure to disable multithreading.

The MATLAB sparse bench

The "sparse bench" in MATLAB changed with Version 7.2. It now uses CHOLMOD (which is about 10 times faster than the old sparse chol), and a much larger sparse matrix. Also, the old sparse bench did not permute the matrix to reduce fill-in, but the new one does. The default ordering changed as well, from SYMMMD to AMD. With all these changes, it is impossible to compare the sparse bench times between Version 7.1 and earlier with Version 7.2 and later. It is even impossible to run the same "bench.m" file in both versions of MATLAB, because the spparms switch that turns off the fill-reducing ordering does so only for the old chol, not the new one. For more details, see Algorithm 8xx: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate.

Copyright, and License:

Copyright (c) 2004-2009. Some portions are Copyright (c) Univ. of Florida. Others are Copyright (c) by their authors (T. A. Davis and W. Hager). Distributed under the GNU LGPL license; the Supernodal and Modify (update/downdate) Modules are distributed under the GNU GPL license.

Availability:

• Download the current version of CHOLMOD here.
• Browse the source code.
• Read the User Guide.
• Requires the UFconfig package.
• Requires the AMD package.
• Requires the COLAMD package.
• Optionally requires the CAMD package.
• Optionally requires the CCOLAMD package.
• Get all of SuiteSparse here.

Other packages required:

• METIS 4.0.1: graph partitioning and sparse matrix ordering. Used by CHOLMOD, but optional.
• LAPACK: linear algebra package. Required by CHOLMOD.
• BLAS: basic linear algebra subprograms. This is the standard reference BLAS. You should use optimized BLAS whenever possible. Used by CHOLMOD and UMFPACK.
• Goto BLAS: typically the fastest BLAS available. Highly recommended for CHOLMOD and UMFPACK.

Versions:

• CHOLMOD-1.7.1.tar.gz (current version)
• CHOLMOD-1.7.0.tar.gz
• CHOLMOD-1.6.0.tar.gz
• CHOLMOD-1.5.0.tar.gz
• CHOLMOD-1.4.0.tar.gz
• CHOLMOD-1.3.0.tar.gz
• CHOLMOD-1.2.0.tar.gz
• CHOLMOD-1.1.1.tar.gz
• CHOLMOD-1.0.0.tar.gz

References (please cite these when using this software):

• Dynamic supernodes in sparse Cholesky update/downdate and triangular solves, T. A. Davis and W. W. Hager, ACM Trans. Math. Software, Vol 35, No. 4, 2009. (as CISE Tech Report)
• Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate , Y. Chen, T. A. Davis, W. W. Hager, and S. Rajamanickam, ACM Trans. Math. Software, Vol 35, No. 3, 2009. (as CISE Tech Report)
• Row modifications of a sparse Cholesky factorization, T. A. Davis and W. W. Hager, SIAM Journal on Matrix Analysis and Applications, vol 26, no 3, pp. 621-639, 2005.
• Multiple-rank modifications of a sparse Cholesky factorization, T. A. Davis and W. W. Hager, SIAM Journal on Matrix Analysis and Applications, vol. 22, no. 4, pp. 997-1013, 2001.
• Modifying a sparse Cholesky factorization, T. A. Davis and W. W. Hager, SIAM Journal on Matrix Analysis and Applications, vol. 20, no. 3, pp. 606-627, 1999.