Research and software development in sparse matrix algorithms:

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

  ---

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

  ---

• SuiteSparse: A Suite of Sparse matrix packages that I have authored or co-authored are available as a single tar or zip file here.
  • 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

    Newly added stand-alone functions (not in the SuiteSparse tar/zip distribution yet):

    • SSMULT: multiplies two MATLAB sparse matrices. Always uses less memory than C=A*B and typically much faster.
    • 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)
    SDMULT	3/08	7.6	mtimes (C=A*B where one of A or B are sparse)

    ---

  • 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 SDMULT (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.

  ---