Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #2617

Parallel Conjugate gradiant solver

Show all headers | View raw

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?sequence=2 


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-system-solver


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.

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Parallel Conjugate gradiant solver Ramine <ramine@1.1> - 2014-10-23 14:02 -0700
  Re: Parallel Conjugate gradiant solver Ramine <ramine@1.1> - 2014-10-23 14:33 -0700

csiph-web