Why Poly((x-6)**100*(2-x)**9000,x) is very slow?

[Paul Royik]

`(x-2)**9000` takes much time, but `(x-6)**100*(2-x)**9000` takes forever.

[Oscar Benjamin]

On Mon, 22 Nov 2021 at 09:18, Paul Royik <distan...@gmail.com> wrote:
>
> `(x-2)**9000` takes much time, but `(x-6)**100*(2-x)**9000` takes forever.

It's slow because it involves explicit coefficient calculations with
very large polynomials. Note that if you don't use Poly and you don't
expand the expressions then it's very fast. This kind of example
pushes towards the limit where the Poly representation is not useful
any more. In other words it's better not to expand these powers and
products but just work with those expressions as they are (which SymPy
can do just fine). I think that it would be useful to have a kind of
Poly representation that does not expand everything but still enables
other Poly methods like `degree`, `coeff` etc to work but that isn't
available so Poly always has to expand everything.

The fastest library I know of for this sort of thing is flint which
can do this in about half a second on this laptop:

In [1]: import flint

In [3]: p1 = flint.fmpz_poly([-6, 1])

In [4]: p1

Out[4]: x + (-6)

In [5]: p2 = flint.fmpz_poly([2, -1])

In [6]: p2

Out[6]: (-1)*x + 2

In [7]: %time _ = p1**100*p2**9000
CPU times: user 597 ms, sys: 58.9 ms, total: 656 ms
Wall time: 665 ms

I won't show the output but it's a 9100 degree polynomial with
coefficients that are 4000 (decimal) digit integers. Note that
although flint can do this example reasonably quickly it's still not
hard to push it a bit further and get something that takes too long or
consumes all the memory in your computer etc. Fundamentally if you
manipulate arbitrarily large non-sparse polynomials in explicit
representations then some things are going to hit up against the
limits of your computer.

I would like to make it so that flint can be used to speed up internal
calculations in SymPy. Otherwise for raw low-level things like this
the fact that SymPy is a pure Python library will typically mean that
even with the best algorithms it will still be about 100x slower than
something like flint which is implemented in a mix of C and assembly
language.

Broadly for two polynomials of degree d1 and d2 the algorithmic
complexity of the basic multiplication algorithm is O(d1 * d2) so
computing (x-6)**100*(2-x)**9000 should be expected to take about 100x
longer than (2-x)**9000. Faster algorithms are based on Karatsuba or
Schönhage–Strassen etc but SymPy doesn't have those. It looks like
flint has a whole bunch implemented:

http://flintlib.org/sphinx/fmpz_poly.html#multiplication
https://fredrikj.net/python-flint/

--
Oscar

[Paul Royik]

Thank you. Yes, in some cases I just need a degree or a leading term.

[Aaron Meurer]

There is this issue about making functions like degree() handle
polynomials in factored form
https://github.com/sympy/sympy/issues/6322. Most things aren't
implemented yet. If you do want just a specific term, your best bet is
to use series(), as this works quite well on polynomials without
expanding them.

Aaron Meurer

> --
> 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 sympy+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/540b2242-930e-43c4-854d-6e1442fc6cf7n%40googlegroups.com.

[Paul Royik]

Thank you!

[Kalevi Suominen]

The degree of a polynomial is the same as the negative the order its pole at `zoo`. That can be obtained by computing the leading term:

    In [41]: f = (x-6)**100*(2-x)**9000

    In [42]: f.subs(x, 1/x).leadterm(x)
    Out[42]: (1, -9100)

Kalevi Suominen

[Paul Royik]

Thank you!