These are chat archives for symengine/symengine

24th
Jan 2016
Isuru Fernando
@isuruf
Jan 24 2016 01:42
@bjodah, yes. I w
I would make the argument std::set, as the order doesn't matter
Ralf Stephan
@rwst
Jan 24 2016 08:40
@bluescarni I just checked timings of operations in mattpap's thesis esp. https://mattpap.github.io/masters-thesis/html/src/internals.html and Sage is way faster, esp. with factorization.
``````sage: R.<x,y,z>=PolynomialRing(ZZ)
sage: f = expand(((x+y+z)**15+1)*((x+y+z)**15+2))
sage: %timeit _ = f.factor()
10 loops, best of 3: 131 ms per loop
sage: %timeit _ = (x^1400-1).factor()
1 loops, best of 3: 862 ms per loop``````
Kalevi Suominen
@jksuom
Jan 24 2016 08:54
@rwst Can you tell which package is Sage using for this factorization?
Ralf Stephan
@rwst
Jan 24 2016 08:56
@jksuom Looks like Singular.
Ralf Stephan
@rwst
Jan 24 2016 09:02
It's a bit surprising because with operations where many conversions to/from Singular is involved Sage's multivar polys are slow. Obviously conversion is less an issue here.
*are involved
Kalevi Suominen
@jksuom
Jan 24 2016 09:09
I think that the algorithms used in SymPy are good, but apparently a C implementation is superior.
Ralf Stephan
@rwst
Jan 24 2016 09:11
With Cython there is still an overhead. That's why I think SymEngine is the better way to speed up SymPy.
Kalevi Suominen
@jksuom
Jan 24 2016 09:12
Yes, I think so too.
Ralf Stephan
@rwst
Jan 24 2016 09:13
The same with Sage, which uses Cython extensively.
Kalevi Suominen
@jksuom
Jan 24 2016 09:14
But using C (or C++) means a lot of work.
Kalevi Suominen
@jksuom
Jan 24 2016 09:26
On second thought, I have a vague recollection that only the core of Singular is in C, and the libraries are in a higher level (Singular?) language. If that is true, it might be useful to take a look at the implementation of factorization in Singular.
Ralf Stephan
@rwst
Jan 24 2016 09:29
Maybe `sympy.polys` is just missing special code for `x^n-1` (factors are cyclotomic).
Francesco Biscani
@bluescarni
Jan 24 2016 10:36
@rwst this paper by Richard Fateman might have some clues, and in general it might have some interesting points about the various options for poly GCD: http://http.cs.berkeley.edu/~fateman/papers/phil8.ps
basically one of his points is that the heuristic GCD works well in Maple because it allows to move the heavy part of the computation into bignum arithmetics
and Maple's interpreted language is slow
so it's a win for them
as they have good bignum implemented (I think GMP probably)
so something similar might apply to Python implementations
he says that if you write your algorithms in a compiled language the relative performances can change quite a bit
Björn Dahlgren
@bjodah
Jan 24 2016 11:04
@isuruf, I was thinking I could sort a `std::vector` to make it canonical (and cheap to do == comparisons). And then maybe provide an alternative constructor taking a `std::set` as an argument?
Isuru Fernando
@isuruf
Jan 24 2016 11:41
@bjodah, yes, `std::vector` is fine as you only need sequential access to the list