back to Tim Davis' home page
other sparse matrix research
UF sparse matrix collection: submissions always welcome.
SuiteSparseQR: multithreaded multifrontal sparse QR factorization

SuiteSparseQR is an implementation of the multifrontal sparse QR factorization
method. Parallelism is exploited both in the BLAS and across different frontal
matrices using Intel's Threading Building Blocks, a sharedmemory programming
model for modern multicore architectures. It can obtain a substantial fraction
of the theoretical peak performance of a multicore computer. The package is
written in C++ with user interfaces for MATLAB, C, and C++.

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 that MATLAB does not exploit the TBB parallelism in SPQR
(as of MATLAB R2012a), however, so you can get better results on a
multicore machine with TBB and your own copy of SPQR.
 INSTALLATION NOTE:
On the Sun Studio C++ compiler, you need to compile with the
features=tmplrefstatic flag.
 Refer to
SuiteSparse
for more installation notes on SPQR.

For
one matrix from the European Space Operations Center (ESOC)
in Germany, x=A\b in MATLAB takes almost 19 hours. Speed is important for this
problem since this is just one part of the reprocessing of 15 years of data.
SuiteSparseQR cuts the time from 19 hours to 6.5 minutes on one core, and 70
seconds on 16 cores. That's an algorithmic speedup of 175, a parallel speedup
of 5.5, and a total speedup of almost 1000. This result is not special; other
large matrices see the same speedup. Memory usage is cut quite a bit too, which
is important because it means larger problems can be solved ... in this case it
could mean giving better orbital estimates of the satellites being tracked.
Copyright, and License:
Copyright (c) 20082012, T. A. Davis.
Distributed under the GNU GPL license.
Availability:
Other packages required:
Versions:
References (please cite these when using this software):