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: Fri, 18 Sep 2009 02:24:03 +0000 (UTC)
Organization: University of Florida
Lines: 54
Message-ID: <h8ur03$1pf$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>
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 1253240643 1839 172.30.248.38 (18 Sep 2009 02:24:03 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 18 Sep 2009 02:24:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 45902
Xref: news.mathworks.com comp.soft-sys.matlab:571241


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message 

> > Sparse matrices are not used to gain speed, but to save
> > space. 
> 
> Wrong, many linear algebra algorithms are designed to gain speed with sparse matrix since Matrix-vector product is much faster than for full matrix. That lead to the class of iterative method (gradient conjugate, GMRES, Lanczos, etc...) that is suitable when working with sparse matrix. The full matrix is not even competitive, even for speed.
> 
> Bruno

Bruno is correct.  Sparse is for performance, both time and memory.  Sure, there are many matrices with too many nonzeros to store as sparse.  Jim Wilkinson's definition of a sparse matrix is one in which it pays to exploit the zeros to save time and memory (he may have said "time and/or memory", but I paraphrase anyway).  Exploiting sparsity can reduce the time needed by many orders of magnitude, depending on the problem.

And in some cases, sparse is even faster than full on a completely nonzero matrix.  Give this a try, and ponder the results.  I ran each twice, to warm up MATLAB (dynamic loading of code).  You need to use R2009b, the latest version, to get these results.

A = rand (2000,1000);
b = rand (2000,1);
tic ; x=A\b ; toc

Elapsed time is 3.069423 seconds.

tic ; x=A\b ; toc

Elapsed time is 2.724363 seconds.

tic ; x=sparse(A)\b ; toc

Elapsed time is 2.120395 seconds.

tic ; x=sparse(A)\b ; toc
Elapsed time is 2.047998 seconds.

sparse(A)\b gets even faster if you turn off its fill-reducing ordering, with

spparms('autoamd',0)
tic ; x=sparse(A)\b ; toc

Elapsed time is 1.910281 seconds.

And  you still get the right answer:

x1=A\b ;
x2=sparse(A)\b ;
norm(x1-x2)/norm(x1)

ans =
   5.2512e-15

in fact, sparse is a teeny bit more accurate in this case, but the difference is small enough to ignore:

>> norm(A'*A*x1-A'*b)
ans =
   2.9924e-11
>> norm(A'*A*x2-A'*b)
ans =
   2.0417e-11