SuiteSparseQR:

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 shared-memory 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++.
• INSTALLATION NOTE: gcc 4.3.x seems to break the memcpy function. For that compiler, you need to add the following line to SuiteSparse/SPQR/Include/spqr.hpp:

  #include <cstring>

  I am in the process of validating/porting that change.

  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) 2008, T. A. Davis. Distributed under the GNU GPL license.

Availability:

• Download the current version of SuiteSparseQR here.
• Browse the source code.
• Read the User Guide.
• Requires the UFconfig package.
• Requires the AMD package.
• Requires the COLAMD package.
• Requires the CHOLMOD package.
• Optionally uses the CAMD package.
• Optionally uses the CCOLAMD package.
• Get all of SuiteSparse here (includes SuiteSparseQR and all packages it depends on)

Other packages required:

• METIS 4.0.1: graph partitioning and sparse matrix ordering. Used by SuiteSparseQR, but optional.
• LAPACK: linear algebra package Required by CHOLMOD.
• BLAS: basic linear algebra subprograms, but be sure to get an optimized BLAS; that link is just for the reference BLAS, which won't be very fast.
• Goto BLAS: typically the fastest BLAS available. Highly recommended for SuiteSparseQR.
• SuiteSparseQR optionally uses Intel's Threading Building Blocks

Versions:

• SPQR-1.1.0.tar.gz (current version)

References (please cite these when using this software):

• SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization, T. A. Davis, submitted to ACM TOMS.
• SuiteSparseQR: Algorithm 8xx: SuiteSparseQR, a multifrontal multithreaded sparse QR factorization package, T. A. Davis, submitted to ACM TOMS.