[GSOC 2012] Matrix Algebra

[Sai Nikhil]

Hi,

Intro: Sai Nikhil, 3rd year Graduate Student. Has enough experience with python programming .

I am following up from various topics list on Sympy-GSoC 2012 ideas page. I found Series, Matrices, Functions modules specifically interesting. I wanted to know which algorithm has been implemented in matrix_multiply function. Is it the Naive Algorithm ? If that were the case, then the running time for the code would be of the order, O(n^3). The element wise multiplication also takes, running time of the order, O(n^3). But Strassen Algorithm would be more efficient compared to this, as the running time is of the order, O(n^lg7)  ≈ O(n^2.807). I wanted to implement it and I need your comments/views in regard to this.

I also submitted my first pull here: https://github.com/sympy/sympy/pull/1130/

Please go through it and tell me if I need to make any edits, so that you can merge it into sympy master .

-thanks,

Sai Nikhil.T

1

[Ronan Lamy]

Le samedi 17 mars 2012 à 20:39 +0530, Sai Nikhil a écrit :
> Hi,
>
>
> Intro: Sai Nikhil, 3rd year Graduate Student. Has enough experience
> with python programming .
>
>
> I am following up from various topics list on Sympy-GSoC 2012 ideas
> page. I found Series, Matrices, Functions modules specifically
> interesting. I wanted to know which algorithm has been implemented in
> matrix_multiply function. Is it the Naive Algorithm ? If that were the
> case, then the running time for the code would be of the order,
> O(n^3). The element wise multiplication also takes, running time of
> the order, O(n^3). But Strassen Algorithm would be more efficient
> compared to this, as the running time is of the order, O(n^lg7) ≈
> O(n^2.807). I wanted to implement it and I need your comments/views in
> regard to this.

Floating-point algorithms aren't useful for sympy. They assume that
multiplication of elements takes a constant time, which is clearly not
true for symbolic or infinite-precision objects. In the case of
Strassen, I think that the recursive multiplication of submatrices
causes the size of the elements to grow very fast.

If you're interested by linear algebra algorithm, you rather look into
fraction-free matrix algorithms, e.g.
http://www.apmaths.uwo.ca/~djeffrey/Offprints/FFLUQR.pdf (already
partially implemented in Matrix.LUdecompositionFF).

>
>
> I also submitted my first pull
> here: https://github.com/sympy/sympy/pull/1130/
>
>
> Please go through it and tell me if I need to make any edits, so that
> you can merge it into sympy master .
>
>
> -thanks,
> Sai Nikhil.T
>
>
> 1

> --
> You received this message because you are subscribed to the Google
> Groups "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to sympy
> +unsub...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/sympy?hl=en.

[mario]

Maybe there is some gain in using Strassen multiplication on Z or Q in gmpy mode.
Attached is an implementation; for matrices with entries randint(0,N)
and size n, I find that for N=10, 10**3, 10**6 the speedup increases with N;
the break even point is n=190; for n=448
the speedup with Strassen in 11% for N=10, 42% for N=1000, 47% for N=10**6