SuiteSparse: a Suite of Sparse matrix packages

Tim Davis, Prof.
Room E338 CSE Building
P.O. Box 116120
University of Florida
Gainesville, FL 32611-6120
352/392-1481
email: my last name AT cise.ufl.edu

This research is supported by the National Science Foundation, Sandia National Laboratories, Google, and NVIDIA.

SuiteSparse as an Ubuntu Linux package

SuiteSparse is used by Google Street View in their Ceres Solver for nonlinear least squares problems.

Used in MATLAB (x=A\b, chol, lu, qr, dmperm, sparse*dense, amd, colamd)

NVIDIA Academic Partner

back to Tim Davis' home page

other sparse matrix research

UF sparse matrix collection: submissions always welcome.

SuiteSparse:

MATLAB_Tools: various m-file utilities , including:
- dimacs10: MATLAB interface for DIMACS10 collection.
- Factorize: object-oriented system solver for MATLAB. An article has been submitted to ACM Transactions on Mathematical Software on this toolbox: Algorithm 9xx, FACTORIZE: an object-oriented linear system solver for MATLAB T. A. Davis, submitted to ACM Transactions on Mathematical Software, 2011.
- sparseinv: sparse inverse subset. There is no specific article or book that discusses this package. To cite it, you could simply use the following:
  - T. Davis, SPARSEINV: a MATLAB toolbox for computing the sparse inverse subset using the Takahashi equations, www.cise.ufl.edu/research/sparse/SuiteSparse, 2011. Also available at MATLAB Central: www.mathworks.com/matlabcentral/fileexchange/33966
- spok: checks if a MATLAB sparse matrix is valid.
- spqr_rank: a toolbox for sparse rank deficient matrices. An article has been submitted to ACM Transactions on Mathematical Software on this toolbox: Algorithm 9xx: Reliable Calculation of Numerical Rank, Null Space Bases, Pseudoinverse Solutions and Basic Solutions using SuiteSparseQR Leslie V. Foster and T. A. Davis, submitted to ACM Transactions on Mathematical Software, 2011.

Click here for a list of known issues/pending changes in the SuiteSparse

Other packages required:

METIS 4.0.1: graph partitioning and sparse matrix ordering. Used by SuiteSparseQR, CHOLMOD, UMFPACK, and KLU, but optional. You can compile these codes without it. The Makefile's automatically detect its presence, and use it if it's available at compile-time. Place a copy of the metis-4.0 directory in the SuiteSparse directory, so that the directory SuiteSparse/metis-4.0/Lib exists. Next, compile metis, and then type "make" in the SuiteSparse directory to compile all of the SuiteSparse.
NOTE: You may encounter an error when compiling METIS on recent Linux systems, caused by METIS' misuse of the double-underscore prefix. There is a system __log2 function that conflicts with the one in METIS. To fix this, edit the metis-4.0/Lib/rename.h file and replace the last line in the file:
```
#define log2				__log2
```
with the following:
```
#define log2				METIS__log2
```
A patch for METIS 5.0.1, from Sean Farley at Argonne National Lab. I haven't tested this yet. It patches SuiteSparse version 3.6.1, not the current version. In a future version of SuiteSparse, I plan on incorporating these changes conditionally, so that SuiteSparse can use either METIS 4.0.1 or 5.0.1.
LAPACK: linear algebra package. Required by SuiteSparseQR and CHOLMOD.
BLAS: basic linear algebra subprograms. This is the standard reference BLAS. You should use optimized BLAS whenever possible. Used by SuiteSparseQR, CHOLMOD and UMFPACK.
Goto BLAS: typically the fastest BLAS available. Highly recommended for SuiteSparseQR, CHOLMOD and UMFPACK.
SuiteSparseQR optionally uses Intel's Threading Building Blocks

Availability:

Versions:

SuiteSparse-3.7.1.tar.gz (current version).
SuiteSparse-3.7.0.tar.gz
SuiteSparse-3.6.1.tar.gz
SuiteSparse-3.6.0.tar.gz
SuiteSparse-3.5.0.tar.gz
SuiteSparse-3.4.0.tar.gz
SuiteSparse-3.3.0.tar.gz
SuiteSparse-3.2.0.tar.gz Major changes: Added SuiteSparseQR (multithreaded multifrontal sparse QR factorization). Minor update to CHOLMOD.
SuiteSparse-3.1.0.tar.gz
SuiteSparse-3.0.0.tar.gz
SuiteSparse-2.4.0.tar.gz
SuiteSparse-2.3.1.tar.gz
SuiteSparse-2.3.0.tar.gz
SuiteSparse-2.1.1.tar.gz

References (please cite these when using this software):

SuiteSparseQR: Algorithm 915: SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization, T. A. Davis, Vol 38, number 1, ACM Transactions on Mathematical Software, 2011.
KLU and BTF:
Algorithm 907: KLU, a direct sparse solver for circuit simulation problems T. A. Davis and E. Palamadai Natarajan, ACM Transactions on Mathematical Software, vol 37, no. 3, 2010.
CSparse, CXSparse, and BTF: Direct Methods for Sparse Linear Systems, T. A. Davis, SIAM, Philadelphia, Sept. 2006. Part of the SIAM Book Series on the Fundamentals of Algorithms.
LDL: Algorithm 849: A concise sparse Cholesky factorization package, T. A. Davis, ACM Transactions on Mathematical Software, vol 31, no. 4, Dec. 2005, pp. 587-591.
COLAMD, CCOLAMD: A column approximate minimum degree ordering algorithm, T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, ACM Transactions on Mathematical Software, vol 30, no. 3, Sept. 2004, pp. 353-376.
COLAMD, CCOLAMD: Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, ACM Transactions on Mathematical Software, vol 30, no. 3, Sept. 2004, pp. 377-380.
AMD, CAMD: Algorithm 837: AMD, An approximate minimum degree ordering algorithm, P. Amestoy, T. A. Davis, and I. S. Duff, ACM Transactions on Mathematical Software, vol 30, no. 3, Sept. 2004, pp. 381-388.
AMD, CAMD: An approximate minimum degree ordering algorithm, P. Amestoy, T. A. Davis, and I. S. Duff, SIAM Journal on Matrix Analysis and Applications, vol 17, no. 4, pp. 886-905, Dec. 1996.
UMFPACK: A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, T. A. Davis, ACM Transactions on Mathematical Software, vol 30, no. 2, June 2004, pp. 165-195.
UMFPACK: Algorithm 832: UMFPACK, an unsymmetric-pattern multifrontal method, T. A. Davis, ACM Transactions on Mathematical Software, vol 30, no. 2, June 2004, pp. 196-199.
UMFPACK: A combined unifrontal/multifrontal method for unsymmetric sparse matrices, T. A. Davis and I. S. Duff, ACM Transactions on Mathematical Software, vol. 25, no. 1, pp. 1-19, March 1999.
UMFPACK: An unsymmetric-pattern multifrontal method for sparse LU factorization, T. A. Davis and I. S. Duff, SIAM Journal on Matrix Analysis and Applications, vol 18, no. 1, pp. 140-158, Jan. 1997.
CHOLMOD: 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.
CHOLMOD: 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.
CHOLMOD: 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.
CHOLMOD: Dynamic supernodes in sparse Cholesky update/downdate and triangular solves, T. A. Davis and W. W. Hager, ACM Trans. Math. Software, to appear.
CHOLMOD: Algorithm 8xx: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate , Y. Chen, T. A. Davis, W. W. Hager, and S. Rajamanickam, ACM Trans. Math. Software, to appear.

Compiling with MS Visual Studio

See Evgenii Rudnyi's article, http://matrixprogramming.com/2008/05/umfpack-vc.