From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: Stability of Cholesky decomposition for a large matrix (~ 30000) Date: 17 Dec 1999 12:16:11 GMT Newsgroups: sci.math.num-analysis In article , Laurent Martin writes: |> Hi, |> |> I'm using Cholesky decomposition to solve Ax=b with A being a sparse |> symmetric definite positive matrix of 1000x1000. I was wondering if |> this very same code could handle problems with A being 30000x30000 |> with around 200,000 non null elements. Is there any problem of |> stability or precision with Cholesky ? If so, what would be a better |> algorithm ? hard to imagine a better algorithm than Cholesky, as long as it is applicable by memory restrictions, provided you want the "exact" solution. Of course, the condition number of the matrix plays a role, but this has little to do with dimension. If your problem comes from finite differences or finite elements (not spectral metohds, wavelets ... ) and you have a quasiregular grid, then cond(A) is in the order of 1/h^2 for a second order elliptic problem, there h is gridsize. Hence a finer grid will yield a worse conditioned matrix. you may estimate the condition number of A by (max l_ii/min l_ii)^2 from below. If this is very large, then precision might be poor, although the residual Ax-b will always be small. (That is an intrinsic property of elimination methods, if correctly applied). But for a problem coming from discretization the "exact" solution of the discrete problem might not be what really is needed. hence a look for multigrid or preconditioned cg-methods might be worthwhile. Nevertheless practioners in FEM use direct solvers with success for dimensions up to hundreds of thousands with no trouble. hope this helps peter ============================================================================== From: jzhang@cs.engr.uky.edu (Jun Zhang) Subject: Re: Stability of Cholesky decomposition for a large matrix (~ 30000) Date: 17 Dec 1999 15:25:32 GMT Newsgroups: sci.math.num-analysis If the matrix is really symmetric positive definite, you should not expect any problem. Cholesky factorization is efficient in both computation and memory consumption. If memory is still a problem, try to reorder the matrix by, say, reverse CM, before factorization to reduce fill-in. The only problem is when the matrix has the smallest eigenvalue very close to zero and your computation is not very accurate due to rounding error. Since in such a case, you may actually dealing with an indefinite matrix. Jun Zhang --------- In article <83d9ib$s9c$3@sun27.hrz.tu-darmstadt.de>, >In article , > Laurent Martin writes: > Hi, > >I'm using Cholesky decomposition to solve Ax=b with A being a sparse >symmetric definite positive matrix of 1000x1000. I was wondering if >this very same code could handle problems with A being 30000x30000 >with around 200,000 non null elements. Is there any problem of >stability or precision with Cholesky ? If so, what would be a better >algorithm ? -- ********************************************************************** * Jun Zhang * E-mail: jzhang@cs.uky.edu * * Department of Computer Science * URL:http://www.cs.uky.edu/~jzhang * * University of Kentucky * Tel:(606)257-3892 * ============================================================================== From: Johannes Subject: Re: Stability of Cholesky decomposition for a large matrix (~ 30000) Date: Tue, 21 Dec 1999 13:10:40 -0800 Newsgroups: sci.math.num-analysis Usually direct methods as Cholesky are more robust, but if the matrix is well conditioned, then Conjugate Gradient with preconditioner might just work. Only a test will tell. CG has the advantage of preserving sparsity. For Cholesky, reordering the matrix is important. It can make a big difference in the nonzero count of the factors G in : A=G'G . Several reordering methods are available, it depends on the structure of A. Sometimes these methods are used in combination. E.g. Incomplete Cholesky. Another trick is 'Iterative refinement' cheap, simple and very effective. Johannes Jive Dadson wrote: > > Jun Zhang wrote: > > ... The original person did not ask advice > > on how to solve a sparse linear system with SPD matrix. > > Oh, but he did: > > > Is there any problem of > > stability or precision with Cholesky ? If so, what would be a better > > algorithm ? > > > > J.