Asp Forum - Parrallel Conjugate gradiant solver

Ramine

10/23/2014 9:03:00 PM

Hello,

I have read this thesis in Mathematis and statistics about
conjugate gradients solver with incomplete Cholesky factorization:

http://repositories.tdl.org/ttu-ir/bitstream/handle/2346/47490/KENNEDY-THESIS.pdf?...

You will notice that the preconditionner with the incomplete Cholesky
factorization will give around 2x to 3x improvement on the number of
iterations...

But as you have noticed i have not used a preconditionner for
my conjugate gradiants system solver cause it's already a parallel solver:

https://sites.google.com/site/aminer68/parallel-implementation-of-conjugate-gradient-linear-sys...

But if you want me to implement a precondtionner that's easy:

So to solve a linear system of linear equations:

A*x = b [1]

we have to first use incomplete Cholesky factorization on A
this will give us A := R*Transpose(R)

Note: Tanspose(R) means the matrix transpose of R
and Inverse(M) means the inverse of the matrix

[1] equal to inverse(M)*A = inverse(M)*b

M is equal to R*Transpose(R)

So after resolving, this will give:

Inverse(Transpose(R))*A*Inverse(R)*R*x = Inverse(Transpose(R))*b

So we have to resolve the following system of equations:

A1*x1=b1

where A1=Inverse(Transpose(R))*A*Inverse(R)

and x1=R*x
and b = Inverse(Transpose(R))*b

So we have to apply the conjugate gradients solver to the system:

A1*x1=b1

And after that we have to resolve the system R*x=x1 to find the vector x

So we have to parallelize the calculation of the determinant of
a matrix to calculate the inverse of a matrix and we have to parallelize
the calculation of the incomplete Cholesky factorization,
and that's not so difficult for me.

That's how the system will be preconditionned to accelerate the
convergence and that's will give a 2x to 3x improvement on the number of
iterations..

And as you have noticed also that i am using arrays to implement my
parallel conjugate gradiant solver, but arrays do take too much memory
even if the matrix is more sparse, but i have decided to implement it
like that with arrays, so a matrix of 100000 by 100000 elements will
take around 64 Gbytes of memory, so you have to have a computer with 32
Gbytes of memory or more to be able to solve large industrial problems
with my parallel Parallel Conjugate gradient linear system solver.
To use much less memory i have to use linklists , but linklists
are not parallel freindly with my parallel algorithm, they will
be too CPU expensive , hence too slow, so this is why i have decided
to keep using arrays in my parallel conjugate gradiant algorithm

Thank you,
Amine Moulay Ramdane.

1 Answer

Ramine

10/23/2014 9:33:00 PM

Hello,

To solve large insdustrial problems , you have to compile my Parallel
conjugate gradient linear system
solver library to a 64bit binary form and you have to have a 32Gbytes of
memory or more in your
computer as i have just explained to you

You can download my Parallel Conjugate gradient system solver library from:

https://sites.google.com/site/aminer68/parallel-implementation-of-conjugate-gradient-linear-sys...

Thank you,
Amine Moulay Ramdane.

comp.programming

Parrallel Conjugate gradiant solver

Ramine

Ramine

x Login to ForumsZone