I am personally not convinced that Karatsuba, Coppersmith-Winograd and Strassen will provide much help here. Basically because only rarely, the size of the problem is the main issue. These algorithms show excellent asymptotic behaviour, but also has an overhead which leads to that quite large problems are needed to actually see a speedup in practice. I can imagine Karatsuba being useful for (non-sparse) polynomial multiplication, but most likely not the other ones, at least for the typical problem sizes I can imagine that people are working with symbolically. In addition, one should investigate the complexity difference between a multiplication and an addition in SymPy. My guess is that the overhead from everything except for the actual computation is much higher than the computation itself and these algorithms (primarily) reduce the number of multiplications and the expense of additions.
(For the record: Karatsuba decreases multiplication from n^2 to n^1.52, Strassen matrix multiplication from n^3 to n^2.83, and Coppersmith-Winograd matrix multiplication for n^3 to n^2.376. For Coppersmith-Winograd I requote from Wikipedia: "However, unlike the Strassen algorithm, it is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware.", and this is for numbers, not symbolic computation, which require even more resources.) BR Oscar Den tis 12 mars 2019 kl 16:55 skrev Shiksha Rawat <[email protected] >: > Thanks for the info Jason Moore and Vishesh Mangla. > > I analyzed the mechanics benchmarks. Many of the commits which are > increasing the computation time are related to ode, printing , matrices. > > I tried to find to find substitute for them. I think LU Decompositon is > used in lagrange.py whose time complexity is O(n^3). but it can be replaced > by better algo like > Coppersmith- Winograd Algorithm(time complexity O(n^2.376)). > > Also as suggested by Vishesh Mangla, Karatsuba fast multiplication and > strassen’s algo can be used for reducing complexity from n^3 to n^1.52. > > Please correct me if I am wrong. I am still analyzing the benchmarks and > trying to find substitutes for other algos. > > > > > On Tue, Mar 12, 2019 at 1:30 AM Vishesh Mangla <[email protected]> > wrote: > >> Well, representation theory is a part of mathematics which maps a matrix >> to a small representation which is easily computable than those big matrix. >> This is also related to block diagonalization. Otherwise Karatsuba fast >> multiplication and strassen’s algo can be used for reducing complexity from >> n^3 to n^1.52. >> >> >> >> Sent from Mail <https://go.microsoft.com/fwlink/?LinkId=550986> for >> Windows 10 >> >> >> >> *From: *Jason Moore <[email protected]> >> *Sent: *12 March 2019 01:26 >> *To: *[email protected] >> *Subject: *Re: [sympy] Gsoc Project idea " Efficient Equation of >> MotionGeneration with Python" discussion. >> >> >> >> >> moorepants.info >> +01 530-601-9791 >> >> >> >> >> >> On Mon, Mar 11, 2019 at 11:44 AM Shiksha Rawat <[email protected]> >> wrote: >> >> Hello, >> >> >> >> I am Shiksha , a second-year undergrad from India. I have been >> contributing to Sympy for more than a month now. While going through Gsoc >> Ideas page, I found Efficient Equation of Motion Generation with Python >> <https://github.com/sympy/sympy/wiki/GSoC-2019-Ideas#classical-mechanics-efficient-equation-of-motion-generation-with-python> >> interesting.I had a subject on engineering mechanics in college and I would >> be pleased if I get a chance to work on it. >> >> >> >> Following are some tasks I want to work on: >> >> *Cleaning Up The CodeBase- *Going through the files like vector.py, >> particle.py , frame.py on which Lagrange.py depends I found that there are >> a number of ways by which we can speed up their computations like >> enumeration is used at places where it is not required. >> >> >> >> Yes this is fine. >> >> >> >> >> >> *Profiling To Find Slow Functions: *Matrices operations take large >> computation time so I think they can we replaced at feasible places with >> some other data structures. >> >> >> >> Matrix operations are likely the best you will get, but we can use more >> efficient matrix calcs if we know the structure and type of matrics. Many >> matrics in EoM derivation are always positive definitive, symmetric, or >> semi-positive definite, etc. >> >> >> >> You can see a couple of mechanics benchmarks here: >> http://www.moorepants.info/misc/sympy-asv/ >> >> >> >> Extensive profiling needs to be done on a variety of mechanics problems >> (big ones preferably) and many speed ups can be made to core algorithms in >> SymPy that will affect mechanics (and other modules too). >> >> >> >> >> >> I am still going through the works done in sympy.mechanics and would >> draft a refined proposal over this and the suggestions I receive. >> >> >> >> Since it is mentioned in the status of that idea that no work is done so >> far, I am not sure where should I start from.I would love to hear from >> mentors as they are more familiar with the topic. >> >> >> >> Links to the issues which I have solved(though not related to current >> idea): >> >> https://github.com/sympy/sympy/pull/15842 >> >> https://github.com/sympy/sympy/pull/15901 >> >> >> >> Thanks. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sympy" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To post to this group, send email to [email protected]. >> Visit this group at https://groups.google.com/group/sympy. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/sympy/CAKVsmS4c_LKAxJ2OoZ%2BjKKcYLyGL45A2s1DfP8g7BT1c-1B%2Bgg%40mail.gmail.com >> <https://groups.google.com/d/msgid/sympy/CAKVsmS4c_LKAxJ2OoZ%2BjKKcYLyGL45A2s1DfP8g7BT1c-1B%2Bgg%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> For more options, visit https://groups.google.com/d/optout. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sympy" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To post to this group, send email to [email protected]. >> Visit this group at https://groups.google.com/group/sympy. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/sympy/CAP7f1AhW07dHr8js%3DNf14DB_azYttbkKY-5mn4ChxGUU0t_pPg%40mail.gmail.com >> <https://groups.google.com/d/msgid/sympy/CAP7f1AhW07dHr8js%3DNf14DB_azYttbkKY-5mn4ChxGUU0t_pPg%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> For more options, visit https://groups.google.com/d/optout. >> >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sympy" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To post to this group, send email to [email protected]. >> Visit this group at https://groups.google.com/group/sympy. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/sympy/5c86be5b.1c69fb81.630b9.8d92%40mx.google.com >> <https://groups.google.com/d/msgid/sympy/5c86be5b.1c69fb81.630b9.8d92%40mx.google.com?utm_medium=email&utm_source=footer> >> . >> For more options, visit https://groups.google.com/d/optout. >> > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at https://groups.google.com/group/sympy. > To view this discussion on the web visit > https://groups.google.com/d/msgid/sympy/CAKVsmS5fEy1g-nwLikObhvLb3ZG6hgZnqTT1gwbCVOMV%3DWn4QA%40mail.gmail.com > <https://groups.google.com/d/msgid/sympy/CAKVsmS5fEy1g-nwLikObhvLb3ZG6hgZnqTT1gwbCVOMV%3DWn4QA%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAFjzj-LcJYs8EJ1WWiSNJKJi8sm_gXqfzTVxUC5DuFAFXh5peA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
