Author 
Message 
Peter Spellucci science forum Guru
Joined: 29 Apr 2005
Posts: 702

Posted: Tue Jul 18, 2006 3:42 pm Post subject:
Re: Complexity of Sparse Cholesky Factorization



In article <1153215982.419020.322920@i42g2000cwa.googlegroups.com>,
"crazyFritz" <crazyFritz@gmail.com> writes:
Quote:  ???? what about the discretized laplacian in 2D: 5 elements not=0 in a
n times n matrix with n to infinity satisfies your statement about sparsity
but cholesky needs O(n^{3/2}) storage and O(n^2) operations
those n log n algorithms are for matrices of special structure
hth
peter
I forgot to claim, that the matrix is in addition symmetric positive
definite, does this change anything?
What kind of additional properties are required to achieve linear
scaling?
Is there any way to do better than the standard Gupta & Kumar?
MfG,
Thomas

no. the discrete Laplacian is positive definite.
of course there are more efficient solvers thna standard cholesky _for this case_
(e.g. using multigrid you get it down to O(log(eps)*n) with precision eps )
but you asked for cholesky
hth
peter 

Back to top 


Evgenii Rudnyi science forum beginner
Joined: 18 Jul 2006
Posts: 1

Posted: Tue Jul 18, 2006 12:28 pm Post subject:
Re: Complexity of Sparse Cholesky Factorization



Quote:  I forgot to claim, that the matrix is in addition symmetric positive
definite, does this change anything?
What kind of additional properties are required to achieve linear
scaling?
Is there any way to do better than the standard Gupta & Kumar?

The work with sparse matrices is always tricky. The speed depends not
only on nnz but also on the matrix connectivity (fillin). As a result,
reordering is crucial to make it fast.
You may want to look at a nice recent message from NAdigest:
http://www.netlib.org/nadigesthtml/06/v06n27.html#5
Best wishes,
Evgenii

http://ModelReduction.com/ 

Back to top 


crazyFritz science forum beginner
Joined: 17 Jul 2006
Posts: 3

Posted: Tue Jul 18, 2006 9:46 am Post subject:
Re: Complexity of Sparse Cholesky Factorization



Quote:  ???? what about the discretized laplacian in 2D: 5 elements not=0 in a
n times n matrix with n to infinity satisfies your statement about sparsity
but cholesky needs O(n^{3/2}) storage and O(n^2) operations
those n log n algorithms are for matrices of special structure
hth
peter

I forgot to claim, that the matrix is in addition symmetric positive
definite, does this change anything?
What kind of additional properties are required to achieve linear
scaling?
Is there any way to do better than the standard Gupta & Kumar?
MfG,
Thomas 

Back to top 


dan1112 science forum beginner
Joined: 15 Jul 2006
Posts: 3

Posted: Tue Jul 18, 2006 6:11 am Post subject:
Re: Complexity of Sparse Cholesky Factorization



Not to hot on the details but I'm fairly sure you can get O(n^(3/2))
complexity wiht nesteddisection schemes
Peter Spellucci wrote:
Quote:  In article <1153143092.493020.268980@35g2000cwc.googlegroups.com>,
"crazyFritz" <crazyFritz@gmail.com> writes:
Assume that for a particular problem it can be proved that the matrices
are getting arbitrarily (even though very slowly) sparse with matrix
size.
Is it justified to claim that a sparse cholesky factorization of such a
matrix can be performed in at most O(NlogN)?
If no why not?
If yes with what specific algorithm?
Can you give a pointer to a particular paper?
Best regards,
Thomas
???? what about the discretized laplacian in 2D: 5 elements not=0 in a
n times n matrix with n to infinity satisfies your statement about sparsity
but cholesky needs O(n^{3/2}) storage and O(n^2) operations
those n log n algorithms are for matrices of special structure
hth
peter 


Back to top 


Peter Spellucci science forum Guru
Joined: 29 Apr 2005
Posts: 702

Posted: Mon Jul 17, 2006 3:32 pm Post subject:
Re: Complexity of Sparse Cholesky Factorization



In article <1153143092.493020.268980@35g2000cwc.googlegroups.com>,
"crazyFritz" <crazyFritz@gmail.com> writes:
Quote:  Assume that for a particular problem it can be proved that the matrices
are getting arbitrarily (even though very slowly) sparse with matrix
size.
Is it justified to claim that a sparse cholesky factorization of such a
matrix can be performed in at most O(NlogN)?
If no why not?
If yes with what specific algorithm?
Can you give a pointer to a particular paper?
Best regards,
Thomas

???? what about the discretized laplacian in 2D: 5 elements not=0 in a
n times n matrix with n to infinity satisfies your statement about sparsity
but cholesky needs O(n^{3/2}) storage and O(n^2) operations
those n log n algorithms are for matrices of special structure
hth
peter 

Back to top 


crazyFritz science forum beginner
Joined: 17 Jul 2006
Posts: 3

Posted: Mon Jul 17, 2006 1:31 pm Post subject:
Complexity of Sparse Cholesky Factorization



Assume that for a particular problem it can be proved that the matrices
are getting arbitrarily (even though very slowly) sparse with matrix
size.
Is it justified to claim that a sparse cholesky factorization of such a
matrix can be performed in at most O(NlogN)?
If no why not?
If yes with what specific algorithm?
Can you give a pointer to a particular paper?
Best regards,
Thomas 

Back to top 


Google


Back to top 


