[Lazarus] fast mathematical matrix operations

classic Classic list List threaded Threaded
20 messages Options
Reply | Threaded
Open this post in threaded view
|

[Lazarus] fast mathematical matrix operations

Andrea Mauri
Dear all,

I am looking for units/packages to deal with numerical matrix
manipulation (typical double type numerical matrices).
I need code able to perform typical matrix operations (e.g. matrix
multiplication, inversion, determinant and so on) as fast as possible
since I deal with big matrices (thousands of rows and columns). I need
it for both windows and linux (32/64).

I found some libraries doing it (e.g. dmath and mrmath).

dmath units (http://sourceforge.net/projects/dmath/) can be used both on
windows and linux but operations are slow on big matrices. calculation
of correlation matrix on a matrix with 3500 rows and 2000 columns get
minutes.

mrmath units (https://github.com/mikerabat/mrmath) is the fastest I
found (just few seconds to calculate correlation matrix on the same data
matrix as before) but is available only for windows and mac os.

any other suggestions? anyone interested in evaluating the possibility
to make mrmath usable under linux too?

thanks,
Andrea

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Michael Schnell
On 06/08/2015 10:57 AM, Andrea Mauri wrote:
>
> I need code able to perform typical matrix operations (e.g. matrix
> multiplication, inversion, determinant and so on) as fast as possible
> since I deal with big matrices (thousands of rows and columns). I need
> it for both windows and linux (32/64).
>

For this it's essential to use the multiple cores the hardware provides.
So the task needs to be distributed to multiple threads.

I once drafted a thread pool unit that night be useful for this (but I
suppose there are other tools that are much more decently tested than
the one I did).

In the FPC/Lazarus mailing lists there already were multiple discussions
on the "parallel loop" issue, but AFAIK, there is no ready-made solution
available yet.

Delphi XE claims to provide such support, though.

-Michael

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Michael Van Canneyt


On Mon, 8 Jun 2015, Michael Schnell wrote:

> On 06/08/2015 10:57 AM, Andrea Mauri wrote:
>>
>> I need code able to perform typical matrix operations (e.g. matrix
>> multiplication, inversion, determinant and so on) as fast as possible since
>> I deal with big matrices (thousands of rows and columns). I need it for
>> both windows and linux (32/64).
>>
>
> For this it's essential to use the multiple cores the hardware provides. So
> the task needs to be distributed to multiple threads.

If you look at the code, you'll see that it does that.

Michael.

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Chris Kelling
In reply to this post by Andrea Mauri
Pascal in general hasn't handled math in an effeceint way. Factorial is a prime example. I would assume that even a 2 dimensial matrix bigger than 10x10 would choke most processes.

It sounds like you would need something made for mathmatical processing like fortran or even lisp. However, taking advantage of parallel processing may give you the speed you are looking for.

On Jun 8, 2015 5:20 AM, Michael Schnell <[hidden email]> wrote:

>
> On 06/08/2015 10:57 AM, Andrea Mauri wrote:
> >
> > I need code able to perform typical matrix operations (e.g. matrix
> > multiplication, inversion, determinant and so on) as fast as possible
> > since I deal with big matrices (thousands of rows and columns). I need
> > it for both windows and linux (32/64).
> >
>
> For this it's essential to use the multiple cores the hardware provides.
> So the task needs to be distributed to multiple threads.
>
> I once drafted a thread pool unit that night be useful for this (but I
> suppose there are other tools that are much more decently tested than
> the one I did).
>
> In the FPC/Lazarus mailing lists there already were multiple discussions
> on the "parallel loop" issue, but AFAIK, there is no ready-made solution
> available yet.
>
> Delphi XE claims to provide such support, though.
>
> -Michael
>
> --
> _______________________________________________
> Lazarus mailing list
> [hidden email]
> http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus 
--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Graeme Geldenhuys-3
In reply to this post by Andrea Mauri
On 2015-06-08 09:57, Andrea Mauri wrote:
> any other suggestions? anyone interested in evaluating the possibility
> to make mrmath usable under linux too?

[disclaimer: I haven't looked at the mrmath code]

I can't think why that would be difficult at all. It should be all
non-gui code, maybe TThread usage. The only possible difficulty I can
see is if ASM was used instead of pure Object Pascal.

Regards,
  - Graeme -

--
fpGUI Toolkit - a cross-platform GUI toolkit using Free Pascal
http://fpgui.sourceforge.net/

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Andrea Mauri
In reply to this post by Michael Van Canneyt
>>
>> For this it's essential to use the multiple cores the hardware
>> provides. So the task needs to be distributed to multiple threads.
>
> If you look at the code, you'll see that it does that.
>

mrmath uses multiple threads and matrix operations are written in asm.
It is the fastest solution I found and it is perfect for my usage but it
does not work on Linux (I think due to the multithread usage but I have
not the capability to work on it, sorry).

Andrea


--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Henry Vermaak
In reply to this post by Andrea Mauri
On Mon, Jun 08, 2015 at 10:57:11AM +0200, Andrea Mauri wrote:
> Dear all,
>
> I am looking for units/packages to deal with numerical matrix
> manipulation (typical double type numerical matrices).
> I need code able to perform typical matrix operations (e.g. matrix
> multiplication, inversion, determinant and so on) as fast as
> possible since I deal with big matrices (thousands of rows and
> columns). I need it for both windows and linux (32/64).

I've heard very good things about Eigen:

https://en.wikipedia.org/wiki/Eigen_%28C%2B%2B_library%29

It's C++ only, though, so you'll have to make a wrapper.

Henry

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

leledumbo
Administrator
In reply to this post by Andrea Mauri
> anyone interested in evaluating the possibility to make mrmath usable under linux too?

Despite it's mostly written in hand-crafted assembly, the code is pretty well commented with respective Pascal construct. You might want to turn it back to Pascal first. My first attempt doesn't yet come to the threading thing, my trunk compiler even stops at:

   cvtsi2sd xmm5, width;

with message:

"ASMMatrixMeanOperationsx64.pas(83,4) Error: Asm: [cvtsi2sd xmmreg,mem128] invalid combination of opcode and operands"

if at least the compiler can go up to the thread pooling, I guess it won't be that difficult to replace the platform specific thread implementations with FPC's native cross platform threading solution. The code is quite good that all thread unit usage are actually abstracted in MtxThreadPool unit functions, so implementing one for linux can also be a solution, albeit not the most beautiful since you have to mess with ifdefs.
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Mark Morgan Lloyd
In reply to this post by Chris Kelling
Chris Kelling wrote:
> Pascal in general hasn't handled math in an effeceint way. Factorial is a prime example. I would assume that even a 2 dimensial matrix bigger than 10x10 would choke most processes.

I don't think this has much to do with Pascal, it's entirely down to the
selection of a suitable algorithm. If you can highlight areas where
(Free) Pascal's parameter passing etc. is deficient I'm sure we're all
interested to discuss it.

> It sounds like you would need something made for mathmatical processing like fortran or even lisp. However, taking advantage of parallel processing may give you the speed you are looking for.

Lisp? LISP?? I'd have thought that the last possible thing that would
have been useful would have been a pure functional system with
occasional "time out" for garbage collection. Now granted that Lisp etc.
was instrumental in popularising analogues of map and reduce, but for
something like brute-force maths, possibly involving OpenMPI etc., there
are more efficient ways of partitioning large chunks of data.

Dmath and mrmath look interesting, subject obviously to accuracy as well
as speed: I've played with matrix stuff in the past which haemorrhaged
digits as soon as you started looking at 1000x1000 or so.

--
Mark Morgan Lloyd
markMLl .AT. telemetry.co .DOT. uk

[Opinions above are the author's, not those of his employers or colleagues]

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Mehmet Erol Sanliturk
In reply to this post by Andrea Mauri


On Mon, Jun 8, 2015 at 1:57 AM, Andrea Mauri <[hidden email]> wrote:
Dear all,

I am looking for units/packages to deal with numerical matrix manipulation (typical double type numerical matrices).
I need code able to perform typical matrix operations (e.g. matrix multiplication, inversion, determinant and so on) as fast as possible since I deal with big matrices (thousands of rows and columns). I need it for both windows and linux (32/64).

I found some libraries doing it (e.g. dmath and mrmath).

dmath units (http://sourceforge.net/projects/dmath/) can be used both on windows and linux but operations are slow on big matrices. calculation of correlation matrix on a matrix with 3500 rows and 2000 columns get minutes.

mrmath units (https://github.com/mikerabat/mrmath) is the fastest I found (just few seconds to calculate correlation matrix on the same data matrix as before) but is available only for windows and mac os.

any other suggestions? anyone interested in evaluating the possibility to make mrmath usable under linux too?

thanks,
Andrea

--
_______________________________________________



Here most important problem is not Pascal or any other programming language but numerical accuracy of the computations .

For large matrices without using multiple precision arithmetic , if matrices are not special types as suitable for good numerical accuracy during computations , i.e. , they are ill-conditioned , the results will be meaningless even if they can be obtained .


Matrix inversion is an n-cube order of operations means , for 1000 rows , computations will be more than ( 1 000 000 000 ) operations . Accumulation of round off errors will be enormous .

( Pascal )
( Python )

or search in Internet

arbitrary precision arithmetic
multiple precision arithmetic


Julia language has multiple precision arithmetic capability .



Thank you very much .


Mehmet Erol Sanliturk



--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Andrea Mauri
In reply to this post by Graeme Geldenhuys-3
>
> I can't think why that would be difficult at all. It should be all
> non-gui code, maybe TThread usage. The only possible difficulty I can
> see is if ASM was used instead of pure Object Pascal.

It is difficult for me ;-) since it uses two different thread
implementations (one for windows and one for MAC OS). I am not
experienced with thread and last time I used assembler was on a z80 in
the '90s when I was a student and I have no memories about it.

I usually use R or matlab to check the consistency calculation and
mrmath seems to work properly.

Andrea

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Graeme Geldenhuys-3
On 2015-06-08 14:29, Andrea Mauri wrote:
>
> It is difficult for me ;-) since it uses two different thread
> implementations (one for windows and one for MAC OS).

Both of those could possible be made obsolete by using FPC's
cross-platform support - even for threading. So you could end up with
one single thread implementation. At least this is how it works for many
FPC + Delphi projects I work on.


> I am not experienced with thread and last time I used assembler was
> on a z80 in the '90s when I was a student and I have no memories
> about it.

I quickly browsed the repository to have a look. There are indeed a lot
of ASM code (to be expected), but it seems it was already ported to FPC,
and targets 32-bit and 64-bit X86 systems. So you got the two most
popular platforms already sorted.

I guess having a pure Object Pascal implementation as a fallback would
be nice, but that is another story.


Regards,
  - Graeme -

--
fpGUI Toolkit - a cross-platform GUI toolkit using Free Pascal
http://fpgui.sourceforge.net/

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Michael Schnell
In reply to this post by Andrea Mauri
On 06/08/2015 03:29 PM, Andrea Mauri wrote:
>
> It is difficult for me ;-) since it uses two different thread
> implementations (one for windows and one for MAC OS).
That is why I mentioned the Thread-pool implementation. It uses just
TThread and hence is as cross-platform as fpc is.

(In fact I suppose there are several more thread-pool units that are
better tested than my proof of concept.)

-Michael


--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Andrea Mauri
Since I am not experienced with thread and actually I am involved in
other projects I cannot work on it.
I am evaluating to propose a bounty (150 euro) to make mrmath fully
compatible with fpc (and working on win 32/64 linux 32/64..).
How can I do that?
I know that there is a page for bounties:
http://wiki.lazarus.freepascal.org/Bounties
how can I propose my bounty?
Anybody interested?

Thanks,
Andrea

Il 09/06/2015 09:42, Michael Schnell ha scritto:

> On 06/08/2015 03:29 PM, Andrea Mauri wrote:
>>
>> It is difficult for me ;-) since it uses two different thread
>> implementations (one for windows and one for MAC OS).
> That is why I mentioned the Thread-pool implementation. It uses just
> TThread and hence is as cross-platform as fpc is.
>
> (In fact I suppose there are several more thread-pool units that are
> better tested than my proof of concept.)
>
> -Michael
>
>
> --
> _______________________________________________
> Lazarus mailing list
> [hidden email]
> http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
>

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Andrea Mauri
In reply to this post by Michael Schnell
Dear all,

I have been on holiday, since I have not seen any answer I try to post
it again.

Since I am not experienced with thread and actually I am involved in
other projects I cannot work on it.
I am evaluating to propose a bounty (150 euro. is is acceptable?) to
make mrmath fully compatible with fpc (and working on win 32/64 linux
32/64..).
How can I do that?
I know that there is a page for bounties:
http://wiki.lazarus.freepascal.org/Bounties

- how can I propose my bounty on the wiki?
- Anybody interested?

Thanks,
Andrea

Il 09/06/2015 09:42, Michael Schnell ha scritto:

> On 06/08/2015 03:29 PM, Andrea Mauri wrote:
>>
>> It is difficult for me ;-) since it uses two different thread
>> implementations (one for windows and one for MAC OS).
> That is why I mentioned the Thread-pool implementation. It uses just
> TThread and hence is as cross-platform as fpc is.
>
> (In fact I suppose there are several more thread-pool units that are
> better tested than my proof of concept.)
>
> -Michael
>
>
> --
> _______________________________________________
> Lazarus mailing list
> [hidden email]
> http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
>

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Mark Morgan Lloyd
Andrea Mauri wrote:

> Dear all,
>
> I have been on holiday, since I have not seen any answer I try to post
> it again.
>
> Since I am not experienced with thread and actually I am involved in
> other projects I cannot work on it.
> I am evaluating to propose a bounty (150 euro. is is acceptable?) to
> make mrmath fully compatible with fpc (and working on win 32/64 linux
> 32/64..).
> How can I do that?

Leledumbo has already demonstrated that the fact that mrmath is written
in assembler is likely to be an insurmountable problem.

If there were a version that was buildable (at least initially) without
using assembler you might get somewhere.

> I know that there is a page for bounties:
> http://wiki.lazarus.freepascal.org/Bounties
>
> - how can I propose my bounty on the wiki?
> - Anybody interested?

Incidentally, have you looked at Vector Pascal
http://www.dcs.gla.ac.uk/~wpc/reports/compilers/compilerindex/x25.html 
The compiler itself is written in Java but the generated code is...
interesting.

--
Mark Morgan Lloyd
markMLl .AT. telemetry.co .DOT. uk

[Opinions above are the author's, not those of his employers or colleagues]

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Andrea Mauri
>
> Leledumbo has already demonstrated that the fact that mrmath is written
> in assembler is likely to be an insurmountable problem.
>
> If there were a version that was buildable (at least initially) without
> using assembler you might get somewhere.

mrmath actually works on MacOSX. why should be a big problem porting to
linux?

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Graeme Geldenhuys-3
On 2015-07-07 13:36, Andrea Mauri wrote:
> mrmath actually works on MacOSX. why should be a big problem porting to
> linux?

Indeed. If you limit the scope to x86 and amd64 CPU's then the port
shouldn't be too hard. Can you confirm is these are the only CPU types
you want to target?

Andrea, I might be interested in the bounty. Let me take a closer look
at mrmath and I'll let you know via email in a day.

Regards,
  - Graeme -

--
fpGUI Toolkit - a cross-platform GUI toolkit using Free Pascal
http://fpgui.sourceforge.net/

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Andrea Mauri
Dear Graeme,

yes, I need it just for x86 and amd64 CPU.
It would be perfect if the actual thread implementation would be unified
using fpc threads. Anyway my first goal is to have a fpc/lazarus
implementation for windows and linux 32/64.

Let me know,
Andrea

Il 07/07/2015 15:10, Graeme Geldenhuys ha scritto:

> On 2015-07-07 13:36, Andrea Mauri wrote:
>> mrmath actually works on MacOSX. why should be a big problem porting to
>> linux?
>
> Indeed. If you limit the scope to x86 and amd64 CPU's then the port
> shouldn't be too hard. Can you confirm is these are the only CPU types
> you want to target?
>
> Andrea, I might be interested in the bounty. Let me take a closer look
> at mrmath and I'll let you know via email in a day.
>
> Regards,
>    - Graeme -
>

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] fast mathematical matrix operations

Luiz Americo Pereira Camara
In reply to this post by Graeme Geldenhuys-3


2015-07-07 10:10 GMT-03:00 Graeme Geldenhuys <[hidden email]>:
On 2015-07-07 13:36, Andrea Mauri wrote:
> mrmath actually works on MacOSX. why should be a big problem porting to
> linux?

Indeed. If you limit the scope to x86 and amd64 CPU's then the port
shouldn't be too hard. Can you confirm is these are the only CPU types
you want to target?


Be aware that calling conventions differ in win64 and non win 64bit.

See "Same 64bit assembly code compiles under windows but not in linux (fpc 260)" and
"win64 calling convention" threads in fpc-devel

Luiz

--
_______________________________________________
Lazarus mailing list
[hidden email]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus