### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: Parallel Gauss-Seidel with relaxation iterative algorithm...  (Read 12821 times)

#### aminer

• Hero Member
• Posts: 956
##### Parallel Gauss-Seidel with relaxation iterative algorithm...
« on: October 31, 2010, 07:09:24 pm »

Hello,

Description:

The Parallel iterative with relaxation method 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 forward elimination process and
is dominated by the O(n^3) back substitution 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 Gauss-Seidel with relaxation iterative algorithm in Object Pascal,
that is very fast.

And please take a look at my article on my Parallel Gauss-Seidel
with relaxation algorithm:

http://pages.videotron.com/aminer/ParallelGaussSeidel/gsrp.htm

The benchmarks here:

http://pages.videotron.com/aminer/ParallelGaussSeidel/gsrp.htm.

Please look at my parallel program gsp.pas inside the zip file , compile and execute it ... -

Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/

Operating Systems: Win , Linux and Mac (x86).

Required FPC switches: -O3 -Sd -dFPC -dWin32 -dFreePascal

-Sd for delphi mode....

Required Delphi switches: -DMSWINDOWS -\$H+

For Delphi 5,6,7 use -DDelphi

For Delphi 2005,2006,2007,2009,2010+ use the switch -DDELPHI2005

Regards,
Amine Moulay Ramdane.
http://pages.videotron.com/aminer/

#### aminer

• Hero Member
• Posts: 956
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #1 on: October 31, 2010, 07:18:06 pm »

I wrote:
[...]
>for example an operation takes 10^9 second

I correct , i mean 10^-9 second.

Welcome:  http://pages.videotron.com/aminer/

Regards,
Amine Moulay Ramdane.

#### Phil

• Hero Member
• Posts: 2750
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #2 on: October 31, 2010, 07:19:10 pm »

Thanks.

-Phil

#### aminer

• Hero Member
• Posts: 956
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #3 on: October 31, 2010, 07:32:43 pm »

Phil wrote:
>Thanks.
>-Phil

Now try it again , it is working:

Welcome:  http://pages.videotron.com/aminer/

Regards,
Amine Moulay Ramdane.

#### aminer

• Hero Member
• Posts: 956
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #4 on: October 31, 2010, 07:46:01 pm »

Hello,

I correct a typo:

It's the forward elimination that takes O(n^3) in the Gauss algorithm...

The Parallel iterative with relaxation method 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 Gauss-Seidel with relaxation iterative algorithm in Object Pascal,
that is very fast.

And welcome: http://pages.videotron.com/aminer/

Regards,
Amine Moulay Ramdane.

#### Phil

• Hero Member
• Posts: 2750
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #5 on: October 31, 2010, 07:54:55 pm »
Crashes on Mac:

An unhandled exception occurred at \$0003A873 :
EAccessViolation : Access violation
\$0003A873  GETTHREADID,  line 126 of /Users/phil/laztests/gsp/LockFreePrimitives.pas
\$0003A662  TGJRINGBUFFER__MEASUREEXECUTIONTIMES,  line 240 of /Users/phil/laztests/gsp/ringbuffer.pas

fpc -O3 -Sd -dFPC -dWin32 -dFreePascal -gl gsr

Also, you might want to regularize your unit/file naming. On a case-sensitive file system, either the unit/file names need to match exactly or else the file names should be all lowercase and FPC will then find them okay. I renamed parallelqueue.pas and ringbuffer.pas.

Thanks.

-Phil

#### aminer

• Hero Member
• Posts: 956
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #6 on: October 31, 2010, 08:27:39 pm »

Hello,

I have tested it on windows(and it is working)
and i forgot to put:

in the uses...

and use the threadpool.pas inside it, and copy
it over the one that is inside gsp.zip , and
tell me if all is correct ?

Regards,
Amine Moulay Ramdane.

#### aminer

• Hero Member
• Posts: 956
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #7 on: October 31, 2010, 08:36:13 pm »

Hello,

I have done it for you Phil..

Note: you have also to delete RingBuffer and RingBufferrb from the uses statement ...

and please tell me if all is ok Phil ?

Welcome: http://pages.videotron.com/aminer/

Regards,
Amine Moulay Ramdane.

#### Phil

• Hero Member
• Posts: 2750
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #8 on: October 31, 2010, 09:27:16 pm »
I moved {\$IFDEF Unix}cthreads,{\$ENDIF} to the beginning of the uses statement in gsr.pas. I believe it needs to go before any unit that uses threads and where you had it in threadpool.pas apparently wasn't earlier enough (nor did moving it to top of threadpool uses).

Now it runs:

The system may or may not converge...
The system converge...
The system solved...
-2.1999999779999871E+0009 -2.0910889788668756E+0009 -2.0490340859696247E+0009

IDEA: It might be interesting if Lazarus users posted some descriptions of projects they're working on. Don't be shy, Laz users. Even if you're working on what you think is fairly mundane, keep in mind Booker T. Washington's famous dictum: "There is as much dignity in plowing a field as in writing a sonnet."

Thanks.

-Phil

#### aminer

• Hero Member
• Posts: 956
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #9 on: October 31, 2010, 09:48:12 pm »

Hello,

I have changed my notation to something like this:

pderivative(u)/pderivative(x1)

That means partial derivatives of function u with respect to x1....

Welcome:

http://pages.videotron.com/aminer/ParallelGaussSeidel/gsrp.htm

http://pages.videotron.com/aminer/

Regards,
Amine Moulay Ramdane.

#### aminer

• Hero Member
• Posts: 956
##### Re: Parallel Gauss-Seidel with relaxation iterative algorithm...
« Reply #10 on: October 31, 2010, 10:03:34 pm »

Phil wrote:
>the beginning of the uses statement in gsr.pas

I have updated gsp.zip with that...

Phil wrote:
>Now it runs:
>The system may or may not converge...
>The system converge...
>The system solved...
>-2.1999999779999871E+0009 -2.0910889788668756E+0009 ->2.0490340859696247E+0009

That means that Parallel Gauss-Seidel with relaxation
algorithm is working on Windows and Mac OSX also

Parallel Gauss-Seidel with relaxation is of great importance
in partial differential equations, splines , Jackson Network
in Queuing theory etc. etc.

Take care,

Amine Moulay Ramdane.