Hello all,

Parallel implementation of Conjugate Gradient Linear

System Solver was updated.

I have corrected a bug so that it works correctly when you useonlya

asingle thread.

Description:

The Parallel implementation of

Conjugate Gradient Linear System Solver that

i programmed here is designed

to be used to solve large sparse systems of

linear equations where the

direct methods can exceed available machine memory

and/or be extremely

time-consuming. for example the direct method of the Gauss

algorithm takes

O(n^2) in the back substitution process and is dominated by

the O(n^3)forward elimination process, that means, if for example an

operation

takes 10^-9 second and we have 1000 equations , the elimination process in

the Gauss algorithm will takes 0.7 second, but if we have 10000 equations

in the

system , the elimination process in the Gauss algorithm will take 11

minutes !.

This is why i have develloped for you the Parallel implementation of

Conjugate

Gradient Linear System Solver in Object Pascal, that is very

fast.

You have only one method to use that is Solve()

function

TParallelConjugateGradient.Solve(var A: arrarrext;var

B,X:VECT;var

RSQ:DOUBLE;nbr_iter:integer;show_iter:boolean):boolean;

The

system: A*x = b

The important parameters in the Solve() method

are:

A is the matrix , B is the b vector, X the initial vector

x,

nbr_iter is the number of iterations that you want

and

show_iter to show the number of iteration on the screen.

RSQ is the sum

of the squares of the components of the residual vector

A.x - b.

I

have got over 3X scalability on a quad core.

The Conjugate Gradient

Method is the most prominent iterative method for

solving sparse systems of

linear equations. Unfortunately, many textbook

treatments of the topic are

written with neither illustrations nor intuition,

and their victims can be found to this day babbling senselessly in the

corners

of dusty libraries. For this reason, a deep, geometric understanding of the

method has been reserved for the elite brilliant few who have painstakingly

decoded the mumblings of their forebears. Conjugate gradient is the most

popular iterative method for solving large systems of linear equations. CG

is

effective for systems of the form A.x = b where x is an unknown vector, b

is

a known vector, A is a known square, symmetric, positive-definite (or

positive-indefinite) matrix.These systems arise in many important settings,

such as finite difference and finite element methods for solving partial

differential

equations, structural analysis, circuit analysis, and math

homework

The Conjugate gradient method can also be applied to non-linear

problems,

but with much less success since the non-linear functions have

multiple

minimums. The Conjugate gradient method will indeed find a minimum

of

such a nonlinear function, but it is in no way guaranteed to be a global

minimum,

or the minimum that is desired.

But the conjugate gradient method is

great iterative method for solving

large,sparse linear systems with a

symmetric, positive, definite matrix.

In the method of conjugate

gradients the residuals are not used as search

directions, as in the

steepest decent method, cause searching can require a

large number of iterations as the residuals zig zag towards the minimum

value for

ill-conditioned matrices. But instead conjugate gradient method

uses the residuals

as a basis to form conjugate search directions . In this manner, the

conjugated

gradients (residuals) form a basis of search directions to minimize the

quadratic

function f(x)=1/2*Transpose(x)*A*x + Transpose(b)*x and to achieve faster

speed and result of dim(N) convergence.

Jacobi serial complexity is

O(N^2) and Conjugate gradient serial complexity

is O(N^3/2).

Please look at the test.pas example inside the zip file, compile and

execute

it...

You can download Parallel implementation of

Conjugate Gradient Linear

System Solver from:

http://pages.videotron.com/aminer

Thank you,

Amine

Moulay Ramdane.