[ublas] Fw: Re: Conjugate gradient method for large sparse matrices

Subject: [ublas] Fw: Re: Conjugate gradient method for large sparse matrices
From: AQMS (azqalidd_at_[hidden])
Date: 2009-02-16 19:20:42

 From: Gunter Winkler <guwi17_at_[hidden]>
 Subject: Re: Conjugate gradient method for large sparse matrices
 To: "azqalidd" <azqalidd_at_[hidden]>
 Date: Monday, February 16, 2009, 11:22 PM
 azqalidd schrieb:
> > Dear Gunter,
> >
> > I am trying to solve a sparse linear system, involving
> very large
> > sparse matrices, at the moment the size of A = 65 000
> * 65 000. and is
> > expected to grow once I extend the usage of my
> program.
> >   
> Are you using the compressed_matrix<..> class? This
> gives the fastest
> results for iterative solvers.
> >
> > I was looking at your example on the following page:
> > http://www.guwi17.de/ublas/examples/
> > This page highlights the usage of the PCG method as an
> iterative solver.
> >
> > At the moment, I am able to solve the system with the
> help of your
> > example - but it's taking rather too long - up to
> 20 seconds.
> >   
> This is really slow. The speed depends on the matrix class,
> the number
> of nonzeros per row (and the sparsity pattern).
> > I am having problem to use the IC preconditioner you
> have proposed in
> > your example, as it fails to converge in a
> considerable amount of time
> > using the IC preconditioner.
> > Therefore, I opt for the diagonal preconditioner.
> >   
> The implementation of the IC is quite bad. There exists
> much better
> preconditioners. However the efficiency strongly depends on
> the matrix
> structure. If you really want to solve big problems then
> you should have
> a look at UMFPack or CXSparse. If you need more iterative
> solvers then
> you should have a look at the ITL
> (http://www.osl.iu.edu/research/itl/).
> I have an interface file for ublas and ITL.
> BTW. as long as you have only a few million unknowns the
> direct solvers
> are better (or not worse) than the iterative solvers.
> > Anyways, I am looking at methods to enhance the speed
> of the convergence.
> >
> > 1) Are there any other preconditioning method
> specifically for very
> > large sparse matrices?
> >   
> Yes and No. The more information about your specific
> problem is used to
> create a preconditioner the better it will get.
> > 2) Do i have to manipulate the existing algorithm (in
> your example
> > program) of the CG method to enhance the speed?
> >   
> The CG does not give much room for improvements. Maybe the
> initial
> prod() could be replaced by an axpy_prod(). Or maybe you
> optimize the
> axpy_prod to take care of symmetry. Anyway - I always
> suggest to use the
> bicg_stab() algorithm (from ITL) because it gives a
> reliable convergence
> (even if the matrix is ill conditioned).
> > 3) Or do I have the manipulate the method implemented
> in the example
> > to exploit the structure of the sparse matrix?
> >   
> You should have a look at the IC - because it can be
> optimized a lot.
> There are quite a lot mathematical papers out there that
> suggest
> improvements.
> > For your information, A is a band diagonal matrix. I
> am also very new
> > to ublas and am not very familiar with its usage.
> >   
> If you have a banded matrix then you should of course use
> the
> banded_matrix<...> class. In this case a full
> Cholesky-Decomposition can
> be made because the decomposition of a banded matrix is
> again a banded
> matrix. (AFAIR with double band width - please check this.)
> 
> mfg
> Gunter
> 
> (PS: If possible, please forward this mail to the ublas
> mailing list.)