FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
Complexity of Sparse Cholesky Factorization
Post new topic   Reply to topic Page 1 of 1 [6 Posts] View previous topic :: View next topic
Author Message
Peter Spellucci
science forum Guru


Joined: 29 Apr 2005
Posts: 702

PostPosted: Tue Jul 18, 2006 3:42 pm    Post subject: Re: Complexity of Sparse Cholesky Factorization Reply with quote

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

PostPosted: Tue Jul 18, 2006 12:28 pm    Post subject: Re: Complexity of Sparse Cholesky Factorization Reply with quote

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 (fill-in). As a result,
reordering is crucial to make it fast.

You may want to look at a nice recent message from NA-digest:

http://www.netlib.org/na-digest-html/06/v06n27.html#5

Best wishes,

Evgenii
--
http://ModelReduction.com/
Back to top
crazyFritz
science forum beginner


Joined: 17 Jul 2006
Posts: 3

PostPosted: Tue Jul 18, 2006 9:46 am    Post subject: Re: Complexity of Sparse Cholesky Factorization Reply with quote

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

PostPosted: Tue Jul 18, 2006 6:11 am    Post subject: Re: Complexity of Sparse Cholesky Factorization Reply with quote

Not to hot on the details but I'm fairly sure you can get O(n^(3/2))
complexity wiht nested-disection 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

PostPosted: Mon Jul 17, 2006 3:32 pm    Post subject: Re: Complexity of Sparse Cholesky Factorization Reply with quote

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

PostPosted: Mon Jul 17, 2006 1:31 pm    Post subject: Complexity of Sparse Cholesky Factorization Reply with 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
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [6 Posts] View previous topic :: View next topic
The time now is Sun Apr 21, 2019 1:01 am | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Complexity of Sparse Cholesky Factorization crazyFritz Research 0 Mon Jul 17, 2006 2:24 pm
No new posts Reductions within P [complexity] ahuznot@yahoo.com Math 0 Sat Jul 15, 2006 4:38 pm
No new posts Bound on nnz for sparse matrix product Scott Kilpatrick num-analysis 3 Wed Jul 12, 2006 4:24 pm
No new posts Algorithm to fit rectangles with different areas inside a... Dani Camps Research 0 Tue Jul 11, 2006 9:14 am
No new posts factorization an NP problem (don't see it) oferlock@yahoo.com Math 4 Thu Jul 06, 2006 4:16 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0423s ][ Queries: 20 (0.0099s) ][ GZIP on - Debug on ]