Will importing sympy and using it for computations be helpful here ? On Thu, Mar 14, 2019 at 2:38 PM Oscar Gustafsson <[email protected]> wrote:
> 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 > <https://groups.google.com/d/msgid/sympy/CAFjzj-LcJYs8EJ1WWiSNJKJi8sm_gXqfzTVxUC5DuFAFXh5peA%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/CAKVsmS4L5q9DXjq5zu2xB2ExatAA53L1kZ%2B4vUjFuYqGirWpjQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
