Path: news.mathworks.com!not-for-mail
From: "Tim Davis" <davis@cise.ufl.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: size(sparse matrix) > size(full matrix)
Date: Mon, 21 Sep 2009 16:59:06 +0000 (UTC)
Organization: University of Florida
Lines: 12
Message-ID: <h98bcq$9va$1@fred.mathworks.com>
References: <8e83f86c-df5e-413d-9943-da36c83a66d2@g1g2000vbr.googlegroups.com> <a56978d9-99f2-4ff6-8073-a77ab61bb6d6@o21g2000vbl.googlegroups.com> <h8t5eb$anh$1@fred.mathworks.com> <h8ur03$1pf$1@fred.mathworks.com> <h901lh$as$1@fred.mathworks.com>
Reply-To: "Tim Davis" <davis@cise.ufl.edu>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1253552346 10218 172.30.248.38 (21 Sep 2009 16:59:06 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 21 Sep 2009 16:59:06 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 45902
Xref: news.mathworks.com comp.soft-sys.matlab:571854


"Derek O'Connor" <derekroconnor@eircom.net> wrote in message 

> Tim, 
> 
> Why is R2009b so fast on x=sparse(A)\b? Has the built-in sparse matrix package been changed from previous versions? Can you tell us how this speed-up has been achieved?
> 
> When I use R2008a, A\b is three times faster than sparse(A)\b.

The new sparse QR uses a multifrontal method (SuiteSparseQR).  For a sparse matrix that's all nonzero, it creates a single dense frontal matrix.  I then use my own dense QR on this, based on LAPACK, but slightly faster than LAPACK.  You can read the details here:

http://www.cise.ufl.edu/~davis/techreports/SPQR/spqr.pdf
http://www.cise.ufl.edu/~davis/techreports/SPQR/algo_spqr.pdf