On Sun, Apr 22, 2012 at 5:08 AM, Tom Bachmann <e_mc...@web.de> wrote: > I implemented a new option "polynomial=True". As explained in the docstring, > this essentially just applies reduced(). If given a polynomial, and using a > graded order (as by default), this is guaranteed to return a *polynomial* > equivalent to what we started with, of minimal degree, but no other > niceties. It seems to work quite well in practice.
Do you have any examples where polynomial=False results in a significantly worse answer? > > Oh and did I mention it handles smallExpr in just under two seconds with > cython enabled? (Producing the same answer as the other two methods). [Note: > the reason why I keep bashing about cython is that otherwise, much > polynomials code, which spends a lot of time converting between > representations anyway, spends quite a bit of that time in the dmp_zero_p > function. Also I use gmpy ground types. Exact timings: Yes, this is the function that I rewrote non-recursively a long time ago, and chopped a whole second off of a seven second integral computation as a result. See 4cb7aa93601c16d26767858175d7b1b4c04e9fca. But even now, it's still linear in the number of generators, and there's no way around that. This shows one of the reasons why the dense representation in the polys is slow. In a sparse representation, testing for zero equivalence would be trivial (assuming we always clear out zero terms, just check if the representation is empty or not---a constant time check). But if there's one function where you can do micro-optimizations and get results, it's this one. I wonder if a for loop would be faster than a while loop, for example. I'm also wondering if the u variable is even needed at all. Also, back when I was looking at it, I wasn't really clever enough to convert many of the recursive functions to non-recursive equivalents. In particular, dmp_from_dict is also used a lot, and is rewritten recursively. If you could figure out how to code this more efficiently, this would almost certainly result in noticeable speedups. > > - cython + gmpy: 1.76 seconds > - gmpy, no cython: 2.54 seconds > - no gmpy, no cython: 2.59 seconds. That's great. How long does the rewrite(exp).expand() method take for you? I guess now we should move on to mediumExpr and largeExpr. For largeExpr, if it finishes at all, I consider that to be a success, since the rewrite(exp) method was taking up all the memory (at least for the person who reported it). > > The ground types mainly matter for groebner basis computations, and for > smallExpr this is not the slowest part.] > > :-) > > > On 21.04.2012 20:52, Aaron Meurer wrote: >> >> I didn't enable cython in the polys, but for me, >> trigsimp_groebner(smallExpr, quick=True, hints=[2]) takes 194 seconds >> in your latest branch. On the other hand, >> smallExpr.rewrite(exp).expand().rewrite(cos).cancel() takes 12 >> seconds, and produces the same answer. >> >> So there's still some work to be done. >> >> Aaron Meurer >> >> On Sat, Apr 21, 2012 at 6:20 AM, Tom Bachmann<e_mc...@web.de> wrote: >>> >>> Ok, so I pushed the changes to my trigsimp branch. There are two commits, >>> WIP and WIP2. >>> >>> The basic idea is the following: suppose there are two sets of variables, >>> x1,..., xn, y1, .., yn, such that none of the xi appears in the >>> generators >>> of the ideal -- they are "free" generators. Then really we have not much >>> hope of ever getting rid of xi-s in the fraction. Specifically, if the >>> fraction is actually a polynomial is the xis, then we cannot ever do >>> better >>> than simplifying just the coefficients. >>> >>> That what WIP implements. >>> >>> Another obervation is that if the coefficients involve different subsets >>> of >>> the the yi-s, then the ratsimp can be sped up further by using only the >>> relevant variables. In fact the groebner basis computed for all variables >>> together can (under reasonable assumptions on the groebner basis >>> computation >>> algorithm) be split according to these disjoint subsets. This is what >>> WIP2 >>> implements (you will notice that doing this splitting is quite a bit of >>> work). >>> >>> Running trigsimp(smallExpr, quick=True, hints=[2]) takes 200 seconds with >>> WIP2 (both ideas), and 250 seconds with WIP (only the first idea). >>> >>> We end up with expressions like sin(q2)*cos(2*q3)*cos(q4) - >>> sin(q2)*cos(q4). >>> Trigsimp_groebner takes forever on this sort of expression - it's just >>> too >>> many variables. There are simpler expressions involving sin(q2+q3) etc, >>> but >>> trigsimp_groebner is bad at finding them (you have to provide them in the >>> hints, essentially...). >>> >>> >>> On 21.04.2012 09:20, Tom Bachmann wrote: >>>> >>>> >>>> Hi, >>>> >>>> I implemented some optimizations (not yet pushed) which allowed me to >>>> run >>>> >>>> trigsimp_groebner(smallExpr, quick=True, hints=[2]) >>>> >>>> in "reasonable" time (~5 minutes). >>>> >>>> The result is this: >>>> >>>> ddq1*(sin(q2)*sin(q4)*cos(2*q3) + cos(q2)*cos(q3)*cos(q4)) - >>>> ddq2*sin(2*q3)*sin(q4) + ddq3*cos(q3)*cos(q4) + ddq4*sin(q3)*sin(q4) + >>>> dq1**2*(-sin(2*q2)*sin(2*q3)*sin(q4)/2 - sin(q3)*cos(2*q2)*cos(q4)) + >>>> dq1*dq3*(-2*sin(q2)*sin(2*q3)*sin(q4) - 2*sin(q3)*cos(q2)*cos(q4)) + >>>> dq1*dq4*(sin(q2)*cos(2*q3)*cos(q4) - sin(q2)*cos(q4)) - >>>> 2*dq2*dq3*sin(q4)*cos(2*q3) - dq2*dq4*sin(2*q3)*cos(q4) - >>>> dq3**2*sin(q3)*cos(q4) + dq4**2*sin(q3)*cos(q4) >>>> >>>> (len(str(smallExpr))/len(str(this)) is about 30!) >>>> >>>> It seems quite possible to run trigsimp_groebner with more aggressive >>>> parameters on this much shorter expression ... but I'll have breakfast >>>> now :-). >>>> >>>> >>>> On 20.04.2012 02:22, Aaron Meurer wrote: >>>>> >>>>> >>>>> Great. I think the best way to demonstrate new functionality like >>>>> this is to just create a special function that does it (like >>>>> trigsimp_groebner) in some branch, and add that to __init__.py. Then, >>>>> when it is ready to go in, remove it from __init__.py and integrate it >>>>> directly into the main function (in this case trigsimp). This is how >>>>> I've done things with risch_integrate in my integration3 branch, and I >>>>> plan to remove it and just put it in integrate() when I'm done. >>>>> >>>>> I tried the expressions from >>>>> https://groups.google.com/d/topic/sympy/3y6orHV2_4k/discussion (see >>>>> the tarball linked to in the first post). I just tried the small >>>>> expression with n=1, but it just hung on the reduction step. Any >>>>> thoughts on how to make this faster? Those expressions would make good >>>>> stress tests for this. >>>>> >>>>> Aaron Meurer >>>>> >>>>> On Thu, Apr 19, 2012 at 3:03 PM, Tom Bachmann<e_mc...@web.de> wrote: >>>>>> >>>>>> >>>>>> I have pushed a more usable trigsimp_groebner to my new trigsimp >>>>>> branch. It >>>>>> is probably buggy, but I've had enough for today. Just to let anyone >>>>>> know >>>>>> who might wish to try it out :). >>>>>> >>>>>> >>>>>> Best, >>>>>> Tom >>>>>> >>>>>> -- >>>>>> 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. >>> >> > > -- > 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.
