Research and software development in sparse matrix algorithms:

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

  ---

• NEWLY RELEASED: SuiteSparseQR: a multithreaded multifrontal sparse QR factorization.

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