Re: Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
- From: "Tim Davis" <davis@xxxxxxxxxxxx>
- Date: Thu, 8 Nov 2007 14:27:23 +0000 (UTC)
"Alessio Rucci" <alessio.rucci@xxxxxxxxx> wrote in message
<fguq3f$ig1$1@xxxxxxxxxxxxxxxxxx>...
I have to solve Ax=b where A is a large sparse matrix (1e+6successful? no.
x 1e+5) with about
7e+6 non-zero elements.
I tried to solve A'Ax=A'b using pcg, but the new matrix
(A'A) is very bad conditioned. I tried to use cholinc to
precondition the system, but A’A has about 1e+7 non-zero
elements, and Matlab gives me out of memory error.
I tried also to solve the system using:
x=(A’A)\(A’b)
but here it is what I get:
sp\: bandwidth = 5864+1+5864.
sp\: is A diagonal? no.
sp\: is band density (0.01) > bandden (0.50) to try banded
solver? no.
sp\: is A triangular? no.
sp\: is A morally triangular? no.
sp\: is A a candidate for Cholesky (symmetric, real positive
diagonal)? yes.
sp\: is CHOLMOD's symbolic Cholesky factorization (with
automatic reordering) successful? yes.
sp\: is CHOLMOD's numeric Cholesky factorization
MC64.
CHOLMOD version 1.1.0, May 5, 2006: : status: ERROR, out of
memory
Architecture: Linux
sizeof(int): 4
sizeof(UF_long): 4
sizeof(void *): 4
sizeof(double): 8
sizeof(Int): 4 (CHOLMOD's basic integer)
sizeof(BLAS_INT): 4 (integer used in the BLAS)
Results from most recent analysis:
Cholesky flop count: 8.0627e+11
Nonzeros in L: 1.9098e+08
memory blocks in use: 11
memory in use (MB): 8.8
peak memory usage (MB): 1961.0
maxrank: update/downdate rank: 8
supernodal control: 1 40 (supernodal if flops/lnz >= 40)
nmethods=0: default strategy: Try user permutation if
given. Try AMD.
Select best ordering tried.
method 0: user permutation (if given)
method 1: AMD (or COLAMD if factorizing AA')
prune_dense: for pruning dense nodes: 10
a dense node has degree >= max(16,(10)*sqrt(n))
flop count: 8.0627e+11
nnz(L): 1.9098e+08
final_asis: TRUE, leave as is
dbound: LDL' diagonal threshold: 0
Entries with abs. value less than dbound are replaced
with +/- dbound.
grow0: memory reallocation: 1.2
grow1: memory reallocation: 1.2
grow2: memory reallocation: 5
nrelax, zrelax: supernodal amalgamation rule:
s = # columns in two adjacent supernodes
z = % of zeros in new supernode if they are merged.
Two supernodes are merged if (s <= 4) or (no new zero
entries) or
(s <= 16 and z < 80%) or (s <= 48 and z < 10%) or (z < 5%)
OK
sp\: But A is real symmetric; try MA57.
MA57 Control Parameters
Ordering used: AMD ordering using MC47.
Block Size for Level 3 BLAS: 16
Merge assembly tree nodes if number of eliminations
is less than: 16
Matrix is scaled using symmetrized version of HSL code
1.000000e-02
Maximum iterative refinement steps: 10
Pivot Threshold:
1.000000e-20
Zero Pivot Tolerance:
6.036817e+08
sp\: is MA57's symbolic analysis successful? yes.
Forecast number of Real entries in factors: 191653054
Forecast number of Integer entries in factors: 1466442
Forecast maximum frontal size: 8071
Number of nodes in Assembly tree: 5001
Forecast length of FACT array (real)
without numerical pivot: 288897514
Forecast length of ifact array (integer)
without numerical pivot 15335967
Length of fact required for a successful
completion of the numerical phase allowing
data compression (without numerical pivoting) 284102031
Length of ifact required for a successful
completion of the numerical phase allowing
data compression (without numerical pivoting) 15335967
Number of data compresses 0
Forecast number of floating point additions
for the assembly processes
7.745417e+11
Forecast number of floating point operations
to perform the elimination operations
counting multiply-add pair as two operations
*** Return code from MA57AD: 1
??? Error using ==> mldivide
Out of memory. Type HELP MEMORY for your options.
Can anyone suggest me a solution or a different strategy to
solve the original problem Ax=b?
Thank you
My last post seems to have gotten lost. Or not.
I clicked "submit" but I got sent to the "update your
profile" page. So this might be a duplicate.
Upload the matrix to http://www.cise.ufl.edu/~web-gfs
and let me take a crack at it. I'd like to add it to
my collection (http://www.cise.ufl.edu/research/sparse).
Send A itself, not A'*A, as a mat file.
x=(A'*A)\(A'*b) is not a good idea, since it is very
ill conditioned. The failure here is CHOLMOD running
out of memory, however. It's puzzling that backslash
then tries MA57. CHOLMOD and MA57 both use AMD, and
the latter tends to use a tad bit more memory. So if
CHOLMOD+AMD runs out of memory, MA57+AMD almost certainly
will.
You should use sparse QR, although that doesn't use
the BLAS and is thus slower than sparse Cholesky.
Try using METIS. There is an interface to the METIS
ordering method in SuiteSparse on the File Exchange.
METIS can give better orderings than AMD, although it
can segfault sometimes :-(
.
- Follow-Ups:
- Re: Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
- From: Alessio Rucci
- Re: Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
- From: Sterren Latsky
- Re: Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
- From: Alessio Rucci
- Re: Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
- References:
- Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
- From: Alessio Rucci
- Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
- Prev by Date: Re: sl classes
- Next by Date: Interpolation of matrix
- Previous by thread: Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
- Next by thread: Re: Solving Ax=b for large sparse matrix(1e+6 X 1e+5) and cholinc failure
- Index(es):
Relevant Pages
|
