cholmod
Comprehensive sparse Cholesky factorization library
Comprehensive sparse Cholesky factorization library
CHOLMOD provides high-performance sparse Cholesky factorization for symmetric positive definite (SPD) and symmetric positive semi-definite matrices. It supports:
Key features:
- Supernodal and simplicial Cholesky (LL' and LDL')
- Fill-reducing orderings: AMD, COLAMD, METIS, CAMD
- Real, complex, and pattern-only matrices
- Single and double precision (float/double)
- Row/column updates and downdates
- GPU acceleration (NVIDIA CUDA)
Typical workflow:
- cholmod_start: Initialize Common workspace
- cholmod_analyze: Symbolic analysis (fill-reducing ordering)
- cholmod_factorize: Numerical Cholesky factorization
- cholmod_solve: Solve Ax = b using the factors
- cholmod_finish: Free workspace
Algorithm
Update/Downdate (rank-k modification): Given L·L' = A, compute L̃ such that L̃·L̃' = A ± C·C':
- Uses Givens rotations for numerical stability
- O(k × nnz(L)) complexity for rank-k modification
For A = L·L': L(j,j) = √(A(j,j) - Σ L(j,k)²) $$L(i,j) = (A(i,j) - Σ L(i,k)·L(j,k)) / L(j,j) \text{ for }i > j$$
Complexity: Factorization: $O(nnz(L)$²/m) with supernodal method Solve: $O(nnz(L)$) per right-hand side Fill-in (nnz(L)) depends on ordering quality
References:
- Davis (2006). "Direct Methods for Sparse Linear Systems". SIAM. ISBN: 978-0-898716-13-9. Chapter 4-8.
- Chen, Davis, Hager, Rajamanickam (2008). "Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate". ACM Trans. Math. Software 35(3).
See Also
- ldl.h for simple LDL' factorization
- amd.h, colamd.h for fill-reducing orderings
- cholmod_finish() to free all workspace at end
- cholmod_start()
- cholmod_finish()
- cholmod_allocate_sparse() to create
- cholmod_triplet for triplet (COO) format
- cholmod_analyze() to create symbolic factor
- cholmod_factorize() to compute numeric factor
- cholmod_solve() to solve using the factor
- cholmod_allocate_dense() to create
- cholmod_solve() to solve with dense right-hand sides
- cholmod_factorize() to compute numerical factorization
- cholmod_analyze_p() to provide a user permutation
- cholmod_analyze()
- cholmod_analyze() for symbolic analysis
- cholmod_solve() to solve using the factorization
- cholmod_factorize()
- cholmod_factorize() to compute the factorization
- cholmod_solve2() for reusable workspace version
- cholmod_solve()
Source
Header file: `CHOLMOD/Include/cholmod.h`