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