Re: [ublas] Modified incomplete cholesky factorization (no fill ins)

Subject: Re: [ublas] Modified incomplete cholesky factorization (no fill ins)
From: AQMS (azqalidd_at_[hidden])
Date: 2009-03-27 09:47:00

Hi Paul,

Thanks for the suggestion on the paper. I will definitely give it a try and will let you know if it works out. 

However, at the moment I am still interested in the MIC(0) factorization method.

This is because, there is a property of MIC(0), in which the row sums of A (from Ax = b) and M (the preconditioner matrix) is the same.

I have somehow managed to force my preconditioner matrix, M = L*transpose(L), where L is a lower triangular matrix which is the result of incomplete cholesky level zero factorization, to have the same rowsums as A. 

I then used this new version of preconditioner matrix, M_new, along with a direct solver for zk = M_new\rk at every iteration of the conjugate gradient just to verify whether it will reduce the number of iterations.

And, it does successfully reduce the number of iterations.
The only thing is, I cant use M_new (the new "forced" preconditioner) directly, since, this will be rather expensive. Rather, I need M_new as a product of L_new and the transpose of L_new. In which I will only be dealing with triangular matrices - and use a trivial forward and backward substitution to solve zk = M_new\rk .

And to do this, I still need to know how to obtain the factorization result from MIC(0).

Note that I find this problem rather interesting since I actually dont have a formal background in iterative solving method - and I found it rather challenging. 

However, I have reached a stage where I am nearing the solution and yet faced with a very final hurdle in finding an efficient way of solving a very large sparse linear system.

Thanks,
Aznul

--- On Fri, 3/27/09, Paul C. Leopardi <paul.leopardi_at_[hidden]> wrote:

> From: Paul C. Leopardi <paul.leopardi_at_[hidden]>
> Subject: Re: [ublas] Modified incomplete cholesky factorization (no fill ins)
> To: azqalidd_at_[hidden], "ublas mailing list" <ublas_at_[hidden]>
> Date: Friday, March 27, 2009, 3:54 PM
> On Wed, 25 Mar 2009, AQMS wrote:
> > At the moment, I am trying to solve a very large
> sparse linear system using
> > preconditioned conjugate gradient method. I've
> tried the incomplete
> > cholesky as a preconditioner, although this was
> successful in reducing the
> > number of iterations to converge, it is possible to
> reduce the iterations
> > even more using the modified incomplete cholesky
> factorization method
> > (MIC).
> > My matrix is both symmetric and positive definite.
> > The reason that I wanted to use the MIC(0) (note that
> the 0 stands for no
> > fill ins) is because I wish to maintain the original
> structure of the
> > matrix.
> > I have read a lot of reference material, however, none
> gave explicit detail
> > on how to perform this method of factorization,
> instead of simply giving a
> > clue of maintaining/ keeping the fill values in the
> diagonal elements by
> > subtracting the fill value from the diagonal element.
> > I've tried this, but I havent managed to get the
> desired result.
> > I know it might not be the correct place to ask this
> question, but I would
> > appreciate if someone might point me in the right
> direction on the sequence
> > of steps to perform this method of factorization.
> 
> Hi Aznul,
> I am not an expert, but I took a quick look at the
> literature and the 
> following paper may interest you:
> 
> Jones, M. T. and Plassmann, P. E. 1995. An improved
> incomplete Cholesky 
> factorization. ACM Trans. Math. Softw. 21, 1 (Mar. 1995),
> 5-17. 
> DOI= http://doi.acm.org/10.1145/200979.200981
> 
> It describes two alternatives to MIC(0) that may be more
> suitable to your 
> needs, and includes pseudocode.
> Best, Paul