Comment #7 on issue 1598 by mattpap: New polynomials manipulation module http://code.google.com/p/sympy/issues/detail?id=1598
Thanks guys for comments. So ... Ondrej: What's really slow in your examples is expand(). See the following phenomenon: In [1]: a = (x+y+sin(z))**20 In [2]: %time b = a.expand() CPU times: user 5.57 s, sys: 0.00 s, total: 5.57 s Wall time: 5.68 s In [4]: %time b = b.expand() CPU times: user 7.77 s, sys: 0.00 s, total: 7.77 s Wall time: 7.90 s Expanding an expanded expression is much slower than the original one. This is slow: In [6]: %time c = factor(b) CPU times: user 12.94 s, sys: 0.00 s, total: 12.95 s Wall time: 13.72 s However you can turn off expanding in Poly or any function in new module by setting `expand=False`, provided you know the input expression is already expanded: In [8]: %time c = factor(b, expand=False) CPU times: user 5.24 s, sys: 0.00 s, total: 5.24 s Wall time: 5.37 s This way you really test efficiency of the factoring algorithm. btw. Creating a Poly instance without expanding is also fast: In [12]: %time p = Poly(b, expand=False) CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s > AssertionError: Test 'test_rootfinding.py' has a duplicate name, (...) OK, so this is py.test bug. I can rename rootfinding to polyroots (or similar). > would you manage to use cython to speed up the factorization a bit? I can, I even started to write pxd declarations for dense*.py but didn't yet run it because of lack of nested defs in Cython. However I can rewrite nested functions, to make Cython happy and experiment, but I don't guarantee that this can be done in one day. Another thing is that I tried your Cython usage in sympy example, but I can't reproduce this great speedup you got. I get only like 30% not an order of magnitude. I will write more about this on the mailing list in the appropriate thread. > Could you beat it? That'd be fun. :) Oh, sure I would be ;) What can be improved? Cython and pure mode is one thing but also factoring algorithm isn't finished yet. Current implementation is focused on correctness not speed and one big branch of Wang's algorithm isn't implemented at all, so improvements are possible. I'm also curious how switching to recursive sparse polynomial representation would affect performance. asmeurer: > Should this rather be "Returns self as if it were an Add instance." Right ;) > How is this routine different than radsimp? This code was a part of Poly.cancel, which was copied from radsimp(). However, radsimp() tries to do more and is problematic (there are issues opened for this). > I tried running a more complex expression through simplify, but it hangs. Yes, but this is once again expand() (or really core problem). Now I see that I should do some hacking and replace expand() (at least partially) with an algorithm based only on polynomials, i.e. replace p**n with Poly(p)**n if p is expanded, replace p_1*p_2*...*p_n with Poly(p_1)*Poly(p_2)*...*Poly(p_n) if p_1,...,p_n are expanded etc. This should be a lot faster. I will also port fast low-level expanding algorithm to polynomials module to replace the current powering algorithm. All this is doable because Basic.as_numer_denom() is fast so I don't have to care about negative exponents. smichr: > but the new module doesn't like reals I does not and rising this exception is intentional. The problem is that some poly algorithms don't care about coefficients, mostly arithmetics, some can work with reals but need special treatment, e.g. div, gcd, and some just won't work, e.g. factorization. Consider all this a work in progress. Soon I will provide an algebra for reals and wrap up mpmath to do computations. The idea is to specify tolerance of computation in this algebra so that zero equivalence could be solved and which would allow division algorithm to work (this is similar to Mathematica Tolerance argument to polynomial manipulation functions). This way computations will be fast and safe. -- You received this message because you are listed in the owner or CC fields of this issue, or because you starred this issue. You may adjust your issue notification preferences at: http://code.google.com/hosting/settings --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "sympy-issues" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sympy-issues?hl=en -~----------~----~----~----~------~----~------~--~---
