Direct Methods for Sparse Linear Systems
Welcome to the web page for
Direct Methods for Sparse Linear Systems,
(informally,
"the sparse backslash book"), by
Tim Davis.
Published by
SIAM as part of the
SIAM Series on the Fundamentals of Algorithms,
in September 2006.
You can
order the book here.
Plans are underway to make the book available as an e-book, via legitimate
and legal channels.
Reviews:
Video:
A plenary talk at the SIAM 2006 Annual Meeting is a concise
synopsis of much of this book.
Below is a copy of
CSparse, a small yet feature-rich sparse matrix package written
specifically for the book. The purpose of the package is to
demonstrate a wide range of sparse matrix algorithms in as concise
a code as possible.
CSparse is about 2,200 lines long (excluding its MATLAB interface, demo codes,
and test codes), yet it contains algorithms (either asympotical optimal
or fast in practice) for all of the following functions described below.
A MATLAB interface is included.
Note that the LU and Cholesky factorization algorithms are not as fast as
UMFPACK or CHOLMOD.
Other functions have comparable performance as their MATLAB equivalents
(some are faster).
Documentation is very terse in the code; it is fully documented in the book.
Some indication of how to call the C functions in CSparse is given by the
CSparse/MATLAB/*.m help files.
To install CSparse and UFget in MATLAB, simply cd to the CSparse/MATLAB
directory in MATLAB, and type
cs_install in
the MATLAB command window. CSparse can also be used in stand-alone
applications via its C-callable interface.
The algorithms contained in CSparse have been chosen with five goals in mind:
- they must embody much of the theory behind sparse matrix algorithms,
- they must be either asymptotically optimal in their run time and memory usage or be fast in practice,
- they must be concise so as to be easily understood and short enough to print in the book,
- they must cover a wide spectrum of matrix operations, and
- they must be accurate (if it says it gets the right answer, then it does) and robust
(it either works, or fails gracefully).
CSparse is concise and simple to understand and thus suitable for a
textbook, yet it is also industrial-strength
software suitable for production use (in fact, the cs_dmperm function now
appears as dmperm in MATLAB 7.5). Industrial-strength software does not
terminate your program if it runs out of memory. Thus, a CSparse routine that
runs out of memory frees any memory it has allocated and returns a null pointer
as the result, in place of the desired result. This out-of-memory condition
can then be handled by the application, which can terminate if it chooses to,
or take some other corrective action instead. If given a null pointer as a
required input parameter, all CSparse functions safely return a null result,
thus protecting against out-of-memory conditions in the caller or in a prior
call to CSparse. CSparse will neither seg-fault nor terminate if it or the
caller runs out of memory.
CSparse includes an exhaustive test suite, which
exercises 100% of the statements in CSparse and also checks all possible ways
that CSparse can run out of memory. The test suite passes all valgrind tests. Part of the purpose of CSparse
is to illustrate methods used in industrial-strength software.
The one
thing lacking in CSparse in this respect is the inclusion of extensive comments
in the C code itself, detailing the purpose of each function, how they work,
and how they are called (see LDL/ldl.c
for a good example of this). This was by design. These comments are present,
but not in the C-callable part of CSparse. Adding them would unduly lengthen
the book. The comments appear in the MATLAB interface. For the C-callable
interface, they appear as the chapters and sections of the book. In that
sense, CSparse has 226 pages of comments ... assuming you buy the book, which
is a reasonable assumption if you'd like to use the code.
For a more
thorough discussion of what it takes to write industrial-strength software, I
highly recommend a recent tech report, Experiences
of sparse direct symmetric solvers by Jennifer
Scott at Rutherford Appleton Lab
and Yifan Hu at Wolfram Research.
Downloads and related links:
Table of contents, and links to related software:
- Chapter 1: Introduction
- 1.1: Linear algebra
- 1.2: Graph theory, algorithms, and data structures
- 1.3: Further reading
- Chapter 2: Basic algorithms
- Chapter 3: Solving triangular systems
- Chapter 4: Cholesky factorization:
- Chapter 5: Orthogonal methods
- Chapter 6: LU factorization
- Chapter 7: Fill-reducing and other orderings
- Chapter 8: Solving sparse linear systems
- Chapter 9: Sparse matrices in CSparse
- Chapter 10: Sparse matrices in MATLAB
- 10.1: Creating sparse matrices:
mesh2d2.m,
mesh2d1.m,
frand.m,
cs_frand_mex.c,
ex_1.m
- 10.2:
Sparse matrix functions and operators
- 10.3: CSparse MATLAB interface:
To install CSparse and UFget in MATLAB, simply cd to the CSparse/MATLAB directory
in MATLAB, and type cs_install in
the MATLAB command window.
- Contents.m
- cs_add.m,
cs_add_mex.c:
sparse matrix addition.
- cs_amd.m,
cs_amd_mex.c:
approximate minimum degree ordering.
- cs_chol.m,
cs_chol_mex.c:
sparse Cholesky factorization.
- cs_cholsol.m,
cs_cholsol_mex.c:
solve A*x=b using a sparse Cholesky factorization.
- cs_counts.m,
cs_counts_mex.c:
column counts for sparse Cholesky factor L.
- cs_dmperm.m,
cs_dmperm_mex.c:
maximum matching or Dulmage-Mendelsohn permutation.
- cs_dmsol.m:
x=A\b using the coarse Dulmage-Mendelsohn decomposition.
- cs_dmspy.m:
plot the Dulmage-Mendelsohn decomposition of a matrix.
- cs_droptol.m,
cs_droptol_mex.c:
remove small entries from a sparse matrix.
- cs_esep.m:
find an edge separator of a symmetric matrix A.
- cs_etree.m,
cs_etree_mex.c:
elimination tree of A or A'*A.
- cs_gaxpy.m,
cs_gaxpy_mex.c:
sparse matrix times vector; a sparse gaxpy.
- cs_lsolve.m,
cs_lsolve_mex.c:
solve a sparse lower triangular system L*x=b.
- cs_ltsolve.m,
cs_ltsolve_mex.c:
solve a sparse upper triangular system L'*x=b.
- cs_lu.m,
cs_lu_mex.c:
sparse LU factorization, with fill-reducing ordering.
- cs_lusol.m,
cs_lusol_mex.c:
solve A*x=b using LU factorization.
- cs_make.m:
compiles CSparse for use in MATLAB.
- cs_mex.c,
cs_mex.h:
utility routines for CSparse mexFunctions.
- cs_multiply.m,
cs_multiply_mex.c
sparse matrix multiply.
- cs_must_compile.m:
utility routine for
cs_make.m
- cs_nd.m:
generalized nested dissection ordering.
- cs_nsep.m:
find a node separator of a symmetric matrix A.
- cs_permute.m,
cs_permute_mex.c:
permute a sparse matrix.
- cs_print.m,
cs_print_mex.c:
print the contents of a sparse matrix.
- cs_qleft.m:
apply Householder vectors on the left.
- cs_qr.m
cs_qr_mex.c
sparse QR factorization.
- cs_qright.m:
apply Householder vectors on the right.
- cs_qrsol.m,
cs_qrsol_mex.c
solve a sparse least-squares problem.
- cs_randperm.m,
cs_randperm_mex.c
random permutation.
- cs_scc.m,
cs_scc_mex.c:
strongly-connected components of a square sparse matrix.
- cs_scc2.m,
strongly-connected components of a square sparse matrix or
a rectangular (bipartite) matrix.
- cs_sep.m:
convert an edge separator into a node separator.
- cs_sparse.m,
cs_sparse_mex.c:
convert a triplet form into a sparse matrix.
- cs_sqr.m,
cs_sqr_mex.c:
symbolic QR factorization.
- cs_symperm.m,
cs_symperm_mex.c:
symmetric permutation of a symmetric matrix.
- cs_thumb_mex.c:
construct a dense thumbnail of a sparse matrix
(for cspy.m).
- cs_transpose.m,
cs_transpose_mex.c:
transpose a real sparse matrix.
- cs_updown.m,
cs_updown_mex.c:
rank-1 update/downdate of a sparse Cholesky factorization.
- cs_usolve.m,
cs_usolve_mex.c:
solve a sparse upper triangular system U*x=b.
- cs_utsolve.m,
cs_utsolve_mex.c:
solve a sparse lower triangular system U'*x=b.
- cspy.m:
plot a sparse matrix in color.
- ccspy.m:
plot the connected components of a matrix.
- 10.4: Examples:
cs_demo1.m,
cs_demo2.m,
cs_demo3.m
- MATLAB mex* and mx* functions
- 10.5: Further reading
- Appendix: Basics of the C programming language
- Bibliography (200 references)
- Index (7 pages)
Click here for beta, current, and older versions of CSparse
Errata and additional exercises
References (please cite these when using this software):