Path: news.mathworks.com!not-for-mail
From: "Tim Davis" <davis@cise.ufl.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: sparse matrix multiplication and cgs()
Date: Tue, 2 Jun 2009 02:01:04 +0000 (UTC)
Organization: University of Florida
Lines: 26
Message-ID: <h0214v$j39$1@fred.mathworks.com>
References: <17247123.13121.1243869597327.JavaMail.jakarta@nitrogen.mathforum.org>
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 1243908064 19561 172.30.248.38 (2 Jun 2009 02:01:04 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 2 Jun 2009 02:01:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 45902
Xref: news.mathworks.com comp.soft-sys.matlab:544091


GS <gshy2014@gamil.com> wrote in message <17247123.13121.1243869597327.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hello, 
>    I solved Ax=b, A is large(of size 2e5), sparse(each row has no more than 26 nonzero), symmetric positive definite matrix. I did it in two ways, 
> 1) L=chol(A,'lower'); tic, x=L\(L'\b),toc;
> 2) tic,[x,flag,resrel,iter]=cgs(A,b,[],n,[],[],x0),toc;
> 
> L is dense, iter=6. So theoretical 2) should be must faster than 1). But 1), 2) ends up with the same time.
> Why?

chol will be much faster if you allow it to permute the matrix (and L will not be dense).  Try:

tic ; [L g q] = chol (A, 'lower') ; toc
tic ; x = q * (L' \ (L \ (q' * b))) ; toc

See also the FACTORIZE object, here: 
http://www.mathworks.com/matlabcentral/fileexchange/24119

which does this for you.  You can speed the forward/backsolve even further by using cs_lsolve for the L\(...) part, and cs_ltsolve for the L'\(...) part. See CSparse on my web page at http://www.cise.ufl.edu/research/sparse.  The L'\(...) solve in MATLAB forms the explicit L transpose, which is slow.  Alternatively, you could just compute LT = L' first, and then do the backslashes.

x=A\b does all this without forming L transpose explicitly. 

THe other problem you have, which is more fundamental, is that your test is printing out the solution x (you have a comma instead of a semicolon).  That dominates the run time, so it's not surprising that both methods take the same amount of time.

You can speed up chol even more by using a better ordering method that isn't in MATLAB (METIS).  CHOLMOD has an interface to it (in SuiteSparse, at the same web page).

In any case, a problem of dimension 2e5 is probably small enough that a direct method will typically be faster ... at least if you allow it to do a fill-reducing ordering.