On 22.04.2012 20:23, Aaron Meurer wrote:
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?
ex = (4*sin(x)*cos(x) + 12*sin(x) + 5*cos(x)**3 + 21*cos(x)**2 +
23*cos(x) + 15) / (-sin(x)*cos(x)**2 + 2*sin(x)*cos(x) + 15*sin(x)
+ 7*cos(x)**3 + 31*cos(x)**2 + 37*cos(x) + 21)
Also something like sin(x)/cos(x) will never be converted to tan(x).
As the docstring says, if you start with a polynomial the resulting
polynomial will have minimal degree. It may have more terms than
necessary (that's true for all algorithm along these lines, and I see no
way around it. That's the biggest problem imho), and there may be
simpler fractions.
The first algorithm in the paper where trigsimp was taken from should
probably do quite well - as far as I can tell it shoud be about as fast
as polynomial=True (maybe two or three times slower, or something of
that order - not 100 times), and work quite well (it minimizes the
maximum of the degrees of numerator and denominator). Will take a bit of
work to implement, though (although it will nicely show of my
commutative algebra module :D).
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).
Sure. That's precisely how sdp and sdm are implemented.
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.
I'll take a look sometime.
I always feel bad micro-optimizing python code because ... well, it's
python. If you want speed, write in in C++ (imho) *g*.
- 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?
7.5 seconds (cython + gmpy - but it is not really sensitive to this).
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).
mediumExpr: 37 seconds with trigsimp(groebner=True, polynomial=True).
Running it a second time only takes 17 seconds - most time is actually
still spent in expand (i.e. conversion), it seems. 54 seconds with
expand. Running with hints=[2] takes 53 seconds.
largeExpr: I killed the rewrite thing after 5 minutes and using 250 mb
memory. The result with trigsimp is similar. It hangs in cancel(), to be
precise. If I remove all references to cancel(), it runs in 150 seconds
(but for all but the most mostrous expressions retaining cancel seems
sensible). We have len(str(largeExpr)) == 200094, len(str(simplified))
== 3203. I also ran it with hint=[2] (but didn't time it - not much
longer I think) and we get len(str(..)) == 3115.
--
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.
