Tim Davis: sparse matrix algorithm research, sparse matrix software, sparse matrix collection

Research and software development in sparse matrix algorithms:

This research is supported by the National Science Foundation, and Sandia National Laboratories.
SuiteSparseQR: a multithreaded multifrontal sparse QR factorization.
Update, Sept 4, 2009: SuiteSparsQR is now QR in MATLAB 7.9, and x=A\b when A is sparse and rectangular. So if you have that version of MATLAB, you already have many of the codes here (UMFPACK for LU, CHOLMOD for CHOL, SuiteSparseQR for QR, SSMULT and SFMULT for A*B, and CSparse for DMPERM.
NOTE: all packages (including older versions) are now available under GNU licenses. Portions of CHOLMOD are GNU GPL; the others are GNU LGPL. This applies to older versions as well, although they may be listed otherwise in their archive files. For a non-GNU license, please contact Tim Davis.
INSTALLATION NOTES:
- UMFPACK, CHOLMOD, and SPQR do not yet work on MATLAB 7.8 and later for 64-bit platforms. This will be corrected shortly (perhaps Nov 20) in SuiteSparse 3.5. Contact me if you would like to try a pre-release of that version. Alternatively, to compile UMFPACK in MATLAB (with the SuiteSparse_install.m or umfpack_install.m script) on a 64-bit computer with 64-bit BLAS (MATLAB 7.8 and later), you need to modify the umfpack_make.m script. At line 79, add the line below. I'll fix this in an upcoming release:
```
    lapack = [lapack ' -DLONG -D''LONGBLAS=UF_long'''] ;
```
  The same holds true for CHOLMOD and SPQR. If you have a 64-bit computer, and MATLAB 7.8 or later, please wait until I port SuiteSparse to that platform.
On the Sun Studio C++ compiler, you need to compile SuiteSparseQR with the -features=tmplrefstatic flag.
SuiteSparse: A Suite of Sparse matrix packages that I have authored or co-authored are available as a single tar or zip file here.
- SuiteSparseQR multithreaded multifrontal sparse QR factorization
- AMD: approximate minimum degree
- CAMD: constrainted approximate minimum degree
- CCOLAMD: constrained column approximate minimum degree
- COLAMD: column approximate minimum degree
- CHOLMOD: sparse supernodal Cholesky factorization and update/downdate
- LDL: a simple LDL^T factorization
- UMFPACK: sparse multifrontal LU factorization
- UFconfig : common configurations (for all but CSparse)
- CSparse,: a concise sparse matrix package a sparse matrix package for my book, Direct Methods for Sparse Linear Systems, published as part of SIAM's book series on the Fundamentals of Algorithms
- CXSparse: CSparse eXtended, with complex matrices and "long" integers,
- RBio: read/write matrices in Rutherford/Boeing format
- BTF: permutation to block triangular form
- KLU: sparse LU factorization, for circuit simulation
- SSMULT: multiplies two MATLAB sparse matrices, now as the MATLAB built-in C=A*B.
- LINFACTOR: a simple MATLAB M-file for solving Ax=b, written to answer the PAQ (Perenially Asked Question) Why not use inv(A) to solve Ax=b?.
- MESHND: creation and nested dissection of regular 2D and 3D meshes.

Packages incorporated into MATLAB by The MathWorks, with versions and MATLAB release dates:

package	date	MATLAB	notes
COLAMD 2.0	9/00	6.0	colamd and symamd
UMFPACK 4.0	7/02	6.5	backslash, slash, and lu
UMFPACK 4.3	9/04	7.0.1	UMFPACK now requires AMD
AMD 1.1	9/04	7.0.1	no user interface, used by UMFPACK
COLAMD 2.4	1/06	7.2
UMFPACK 4.6	1/06	7.2
AMD 1.2	1/06	7.2
CHOLMOD 1.0	1/06	7.2	chol, backslash, slash, etree, and symbfact.
UMFPACK 5.0	8/06	7.3
AMD 2.0	8/06	7.3	amd
COLAMD 2.5	8/06	7.3
CHOLMOD 1.1	1/07	7.4
CSparse	8/07	7.5	dmperm
SSMULT	3/08	7.6	mtimes (C=A*B, where both A and B are sparse)
SFMULT	3/08	7.6	mtimes (C=A*B where one of A or B are sparse and the other is dense)
SuiteSparseQR (SPQR)	9/09	7.8	backslash, slash, and qr

Pending changes, known issues in SuiteSparse packages:
- Add CHOLMOD nested dissection ordering, and METIS ordering, to UMFPACK.
- Add Paraklete, a parallel sparse LU (under development)
- Add Banded reduction to bidiagonal (identical features as LAPACK's DGBBRD, but 5 times faster)
- Add Sparse SVD (under development)
- Add SFMULT (sparse matrix times dense matrix); already incorporated into MATLAB 7.6.
University of Florida sparse matrix collection Includes a MATLAB interface. Send me your matrices..
Collaboration with Bill Hager modifying a sparse Cholesky factorization, graph partitioning, and optimization.
A comparison of simplex method algorithms, by Steve Morgan. (a comment about the design of one of the routines).

Books:

MATLAB Primer - 7th Edition, CRC Press.
Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, Sept 2006.