Re: inverse symmetric matrix

Hi all,
Sorry to chime in at this late stage, but this is one other thing you may want 
to consider. If the original matrix is ordered in such a way that the 
complete Cholesky factorization produces a high amount of fill, and the 
original matrix is poorly conditioned, then a reordering of the matrix 
*might* improve the performance the incomplete cholesky or the conjugate 
gradient, or both. It *might* also make performance worse.

See, eg. Iain S. Duff and G.A. Meurant,
The effect of ordering on preconditioned conjugate gradients. BIT 29, 
635--657, 1989.
Iain S. Duff, Henk A. van der Vorst,
Preconditioning and Parallel Preconditioning (1998)
http://citeseer.nj.nec.com/duff98preconditioning.html and further references 
at http://citeseer.nj.nec.com/context/61878/0

For reorderings, see, eg. Matlab symmmd at
http://www.mathworks.com/access/helpdesk/help/techdoc/ref/symmmd.shtml and
Sparse Matrices in MATLAB: Design and Implementation (1991) 
http://citeseer.nj.nec.com/gilbert91sparse.html
Best regards

On Tue, 10 Jun 2003 03:34, Yasser H. Abdel-Haleem wrote:
> Hi,
> My code is related to optimization and I used a code was available for
> testing suite.
> 
> typedef matrix<double, 
>                symmetric<lower>, 
>                array< compressed<> >, 
>                column_major>::type SDMATRIX;
> 
> int max_iter = 256;
> itl::cholesky<SDMATRIX> precond(mfSymmMatrix);
> itl::noisy_iteration<double> iter(vfGradient, max_iter, 1e-6);
> itl::cg(mfSymmMatrix, vfDelta, vfGradient, precond(), iter);
> 
> I am not sure about the result (I do not mean to) as I have test
> environment with 5*5 matrix. I am planning to use to for matrix from
> (500 up to 1000 dimension matrices). I guess the difference may be clear
> for large matrices.
> 
> So, you recommend using CG for the fastest results. One more question if
> I change array< compressed<> > to dense<>, the templates are not able to
> generate a valid code and the compilation stops. 
> 
> 
> Thanks and best regards,
> Yasser
> -----Original Message-----
> From: [email protected] [mailto:[email protected]] 
> Sent: Monday, June 09, 2003 1:13 AM
> To: General Matrix Template Library (MTL) list
> Subject: RE: MTL: inverse symmetric matrix
> 
> 
> Hi -- the standard method for iterative solution of sparse SPD is to
> use preconditioned CG.  How well this will work depends strongly on
> your preconditioner.  If your problem is elliptic, then an incomplete
> Cholesky preconditioner is probably a pretty good bet.
> 
> It is surprising that lu_inv would be faster since lu is an N^3
> algorithm.  Preconditioned CG should be much faster than that.  How
> large is your problem?  What kind of matrix are you using for the CG
> algorithm?
> 
> 
> In our last exciting episode "Yasser H. Abdel-Haleem" wrote:
> > Importance: Normal
> 
> > Hi,
> 
> > Thanks for your reply. Your comment was helpful. I was able to make my
> > problem work as A*x=b. Hence, I was able to use ITL to get the X
> vector
> > directly. However, I have some comments.
> > 1- If I use lu_inv(A) * b, the consumed time was less than for cg
> > method.
> > 2- The method cgs required the same amount of time of cg. I use
> Cholesky
> > pre-conditioner in both cg, cgs methods. 
> 
> > I wonder why I got slower performance with cg, cgs for the symmetric
> > matrix relative to lu_inverse or this is normal.
> 
> > Can any one suggest an iterative method that is fast for PD symmetric
> > matrix? I use VC++ version 6.0.
> 
> > Thanks in advance,
> > Yasser
> >  
> 
> 
> > -----Original Message-----
> > From: Gunter Winkler [mailto:[email protected]] 
> > Sent: Thursday, June 05, 2003 8:05 AM
> > To: General Matrix Template Library (MTL) list
> > Subject: Re: MTL: inverse symmetric matrix
> 
> > Yasser H. Abdel-Haleem wrote:
> > > Hi,
> > 
> > > I would like to get the inverse of a symmetric matrix. Currently, I
> > copy 
> > > it to a dense matrix and get the inverse using LU inverse.  However,
> I
> 
> > > search a very fast method to do that directly without this
> > intermediate 
> > > step. Can any one suggest a solution?
> 
> > For symmetric matrices you should use the Cholesky-Factorization 
> > (similar to LU: A = L L^T) I don't know if someone implemented it 
> > already for MTL, but google gives lots if information about that.
> 
> > mfg
> > Gunter
> 
> 
> > _______________________________________________
> > This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/
> 
> 
> Kind Regards,
> Andrew Lumsdaine
> 
> _______________________________________________
> This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/
> 

_______________________________________________
This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/