MATLAB Central Newsreader - SuiteSparseQR: a multithreaded multifrontal sparse QR factorization

SuiteSparseQR: a multithreaded multifrontal sparse QR factorization

Tim Davis — Wed, 24 Sep 2008 23:55:03 -0400

I would like announce the release of a new multithreaded multifrontal sparse QR factorization package, SuiteSparseQR.
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. SuiteSparseQR 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++.

Its MATLAB interface is upward-compatible with the qr function in MATLAB and x=A\b when A is rectangular. It can also handle complex matrices, and it can return Q as a concise set of sparse Householder vectors in a MATLAB struct (nnz(Q) can very high for Q as a matrix; by contrast, nnz(Q.H) is often less than nnz(R)).

You can download the code here (with a GNU GPL license):

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=12233&objectType=FILE

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.

Re: SuiteSparseQR: a multithreaded multifrontal sparse QR factorization

John D'Errico — Thu, 25 Sep 2008 10:32:01 -0400

"Tim Davis" <davis@cise.ufl.edu> wrote in message <gbek0n$697$1@fred.mathworks.com>...
> I would like announce the release of a new multithreaded multifrontal sparse QR factorization package, SuiteSparseQR.
> 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. SuiteSparseQR 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++.
>
> Its MATLAB interface is upward-compatible with the qr function in MATLAB and x=A\b when A is rectangular. It can also handle complex matrices, and it can return Q as a concise set of sparse Householder vectors in a MATLAB struct (nnz(Q) can very high for Q as a matrix; by contrast, nnz(Q.H) is often less than nnz(R)).
>
> You can download the code here (with a GNU GPL license):
>
> http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=12233&objectType=FILE
>
> 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.

NEAT!

John

Re: SuiteSparseQR: a multithreaded multifrontal sparse QR factorization

Thomas Clark — Thu, 25 Sep 2008 21:10:17 -0400

Its pretty difficult to express wonder and joy through the newsreader... But believe me, they're being felt.

Thanks for all your good work on this subject Tim, I've learned a lot from watching your posts here and through your FEX submissions.

Kindest regards :)

Tom Clark

Re: SuiteSparseQR: a multithreaded multifrontal sparse QR factorization

Tim Davis — Fri, 26 Sep 2008 10:51:02 -0400

"Thomas Clark" <t.clarkremove_spam@cantab.net> wrote in message <gbgunp$9ug$1@fred.mathworks.com>...
> Its pretty difficult to express wonder and joy through the newsreader... But believe me, they're being felt.
>
> Thanks for all your good work on this subject Tim, I've learned a lot from watching your posts here and through your FEX submissions.
>
> Kindest regards :)
>
> Tom Clark

Thanks for the kind note. It's been quite a fun project to work on. "... and when I run, I feel His pleasure" (Eric Liddell, http://www.imdb.com/title/tt0082158/quotes ).

A side note ... if you are on Windows and use just the "lcc" compiler that comes with MATLAB, you can't compile the code. You need to get a C++ compiler. Microsoft Visual Studio C++ Express Edition works fine, and it's a free download. Details are in the User Guide.