Search   Memberlist   Usergroups
 Page 1 of 1 [6 Posts]
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

"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 )
hth
peter
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 (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/
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
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 nested-disection schemes
Peter Spellucci wrote:
 Quote: In article <1153143092.493020.268980@35g2000cwc.googlegroups.com>, "crazyFritz" 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
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

"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
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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [6 Posts]
 The time now is Sun Apr 21, 2019 1:01 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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