Path: news.mathworks.com!not-for-mail
From: "Tim Davis" <davis@cise.ufl.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
Date: Tue, 13 Nov 2007 12:53:30 +0000 (UTC)
Organization: University of Florida
Lines: 27
Message-ID: <fhc6oa$nqc$1@fred.mathworks.com>
References: <fguq3f$ig1$1@fred.mathworks.com> <fgv6cb$2c5$1@fred.mathworks.com> <fgv898$6fk$1@fred.mathworks.com> <fgv96r$oov$1@fred.mathworks.com> <fhc479$lj5$1@fred.mathworks.com>
Reply-To: "Tim Davis" <davis@cise.ufl.edu>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1194958410 24396 172.30.248.37 (13 Nov 2007 12:53:30 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 13 Nov 2007 12:53:30 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 45902
Xref: news.mathworks.com comp.soft-sys.matlab:437280


I was able to solve it with a direct method, on my Pentium 4
which has 4GB of memory and a 3.2GHz clock cycle.

[x stats] = cholmod2 (A'*A, A'*b) ;
r = norm (A'*(A*x) - A'*b) ;

where b=rand(size(A,1),1) ;

CHOLMOD in this case is using the best of AMD or METIS.  You
need to install CHOLMOD from the SuiteSparse on the File
Exchange to do this; METIS is not in MATLAB itself.

CHOLMOD got an rcond of 4e-5, so this is not too
ill-conditioned to use the normal equations (CHOLMOD's
condition estimate is 1/4e-5 or about 2e4).  nnz(L) was 115
million.  The flop count was 283 billion.  Time was 94.7
seconds (CHOLMOD got 3 Gflops, or just less than 50% of the
theoretical peak.  Total memory usage was 1283 MB, or about
1.3 GB.  So if you have a machine, with say 2GB of main
memory, that should be sufficient.

Your results may vary ... please send me your b vector. 
This problem is incomplete without it, and iterative solvers
cannot be tested without b.

Using AMD within CHOLMOD isn't sufficient because the fillin
is worse and the memory usage is too high.