- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
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,
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,
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
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
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
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).
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.
it...
You can download Parallel implementation of Conjugate Gradient Linear
System Solver from:
http://pages.videotron.com/aminer
Thank you,
Amine Moulay Ramdane.
Link Copied
0 Replies
Reply
Topic Options
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page