Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

PolynomialDivisionFailed in integrate #18386

Open
e00E opened this issue Jan 19, 2020 · 10 comments
Open

PolynomialDivisionFailed in integrate #18386

e00E opened this issue Jan 19, 2020 · 10 comments

Comments

@e00E
Copy link

e00E commented Jan 19, 2020

x = sympy.Symbol("x")
a = sympy.Symbol("a")
f = x**2 + a/(x + 1.1)
g = abs(x)
sympy.integrate((g - f)**2, (x, -1, 0))
  File "/usr/lib/python3.8/site-packages/sympy/integrals/integrals.py", line 1522, in integrate
    return integral.doit(**doit_flags)
  File "/usr/lib/python3.8/site-packages/sympy/integrals/integrals.py", line 464, in doit
    did = self.xreplace(reps).doit(**hints)
  File "/usr/lib/python3.8/site-packages/sympy/integrals/integrals.py", line 575, in doit
    antideriv = self._eval_integral(
  File "/usr/lib/python3.8/site-packages/sympy/integrals/integrals.py", line 906, in _eval_integral
    result, i = risch_integrate(f, x, separate_integral=True,
  File "/usr/lib/python3.8/site-packages/sympy/integrals/risch.py", line 1752, in risch_integrate
    fa, fd = fa.cancel(fd, include=True)
  File "/usr/lib/python3.8/site-packages/sympy/polys/polytools.py", line 3689, in cancel
    result = F.cancel(G, include=include)
  File "/usr/lib/python3.8/site-packages/sympy/polys/polyclasses.py", line 695, in cancel
    F, G = dmp_cancel(F, G, lev, dom, include=True)
  File "/usr/lib/python3.8/site-packages/sympy/polys/euclidtools.py", line 1869, in dmp_cancel
    _, p, q = dmp_inner_gcd(f, g, u, K)
  File "/usr/lib/python3.8/site-packages/sympy/polys/euclidtools.py", line 1583, in dmp_inner_gcd
    return dup_inner_gcd(f, g, K)
  File "/usr/lib/python3.8/site-packages/sympy/polys/euclidtools.py", line 1523, in dup_inner_gcd
    return dup_rr_prs_gcd(f, g, K)
  File "/usr/lib/python3.8/site-packages/sympy/polys/euclidtools.py", line 994, in dup_rr_prs_gcd
    h = dup_subresultants(F, G, K)[-1]
  File "/usr/lib/python3.8/site-packages/sympy/polys/euclidtools.py", line 405, in dup_subresultants
    return dup_inner_subresultants(f, g, K)[0]
  File "/usr/lib/python3.8/site-packages/sympy/polys/euclidtools.py", line 375, in dup_inner_subresultants
    h = dup_prem(f, g, K)
  File "/usr/lib/python3.8/site-packages/sympy/polys/densearith.py", line 1095, in dup_prem
    raise PolynomialDivisionFailed(f, g, K)
sympy.polys.polyerrors.PolynomialDivisionFailed: couldn't reduce degree in a polynomial division algorithm when dividing [-0.22*a - 2.39364084109184e-15, -a**2 - 0.242*a - 2.20312657006616e-15] by [a**4 - 1.11022302462516e-16*a**3 - 8.67361737988404e-16*a**2 - 1.97215226305253e-31*a + 1.84795400213452e-31]. This can happen when it's not possible to detect zero in the coefficient domain. The domain of computation is RR[a]. Zero detection is guaranteed in this coefficient domain. This may indicate a bug in SymPy or the domain is user defined and doesn't implement zero detection properly.

Depends on the 1.1 constant. Some values error, some don't.

I am using sympy 1.5.1 on arch linux.

@oscarbenjamin
Copy link
Contributor

It works with Rational rather than Float:

In [5]: x = sympy.Symbol("x") 
   ...: a = sympy.Symbol("a") 
   ...: f = x**2 + a/(x + Rational(11, 10)) 
   ...: g = abs(x) 
   ...: sympy.integrate((g - f)**2, (x, -1, 0))                                                                                                
Out[5]: 
     2                          
100a    6a   11alog(11)   1 
────── - ─── + ──────────── + ──
  11      5         50        30

@rursprung
Copy link

i ran into the same problem, i've attached an interactive python notebook with which to reproduce my case: reproduction.ipynb.txt (GitHub doesn't allow uploading .ipynb files => remove the .txt after downloading it). as i already ran the cells you can see the output produced on my system or you can run it again to see what happens on your system.

my workaround (i didn't find this ticket until after) was to use sympy variables instead of floats, do the integration and only then substitute in the real values. this makes it of course more cumbersome but at least it works.

this was with SymPy 1.10.1 and python 3.8.13

(if you prefer to have an own ticket for my case i can also raise a separate one; but i presume based on the description that it's the same as it's the same error and also caused by floats).

@oscarbenjamin
Copy link
Contributor

if you prefer to have an own ticket for my case i can also raise a separate one

I think it's good to add the example here. It would be better just to paste a short demonstration as a code block like in the OP though (rather than attaching a notebook).

@rursprung
Copy link

rursprung commented Jul 4, 2022

ok, there you go:

python code
import sympy as sym
import scipy.constants as const
from IPython.display import display,Math

a = 2.4e-2 # m
Q1 = 10e-9 # C
Q2 = -10e-9 # C

x = sym.symbols('x', real=True, positive=True)

P1 = 2*a
P2 = 1*a

r1 = sym.sqrt(a**2 + x**2)
E1 = 1/(4*const.pi*const.epsilon_0) * Q1 / r1**2 * 1
r2 = sym.sqrt(a**2 + (-3*a + x)**2)
E2 = 1/(4*const.pi*const.epsilon_0) * Q2 / r2**2 * -1 # direction is inversed

E = E1 + E2

display(Math('E = ' + sym.latex(E)))

U = E.expand().integrate((x,P1,P2))

display(Math(r'U \approx %.2f~\mathrm V' %U))

qe = -const.elementary_charge
dW = qe * U

display(Math(r'\Delta W \approx %.2f \cdot 10^{-16}~\mathrm J' %(dW * 1e16)))
error message & stack trace
---------------------------------------------------------------------------
PolynomialDivisionFailed                  Traceback (most recent call last)
Input In [4], in <cell line: 16>()
     13 display(Math('E = ' + sym.latex(E)))
     15 # <E,e_x> = E[0]
---> 16 U = E.expand().integrate((x,P1,P2))
     18 display(Math(r'U \approx %.2f~\mathrm V' %U))
     20 qe = -const.elementary_charge

File ~\anaconda3\lib\site-packages\sympy\core\expr.py:3668, in Expr.integrate(self, *args, **kwargs)
   3666 """See the integrate function in sympy.integrals"""
   3667 from sympy.integrals.integrals import integrate
-> 3668 return integrate(self, *args, **kwargs)

File ~\anaconda3\lib\site-packages\sympy\integrals\integrals.py:1566, in integrate(meijerg, conds, risch, heurisch, manual, *args, **kwargs)
   1563 integral = Integral(*args, **kwargs)
   1565 if isinstance(integral, Integral):
-> 1566     return integral.doit(**doit_flags)
   1567 else:
   1568     new_args = [a.doit(**doit_flags) if isinstance(a, Integral) else a
   1569         for a in integral.args]

File ~\anaconda3\lib\site-packages\sympy\integrals\integrals.py:613, in Integral.doit(self, **hints)
    611     antideriv = None
    612 else:
--> 613     antideriv = self._eval_integral(
    614         function, xab[0], **eval_kwargs)
    615     if antideriv is None and meijerg is True:
    616         ret = try_meijerg(function, xab)

File ~\anaconda3\lib\site-packages\sympy\integrals\integrals.py:956, in Integral._eval_integral(self, f, x, meijerg, risch, manual, heurisch, conds, final)
    954 if risch is not False:
    955     try:
--> 956         result, i = risch_integrate(f, x, separate_integral=True,
    957             conds=conds)
    958     except NotImplementedError:
    959         pass

File ~\anaconda3\lib\site-packages\sympy\integrals\risch.py:1835, in risch_integrate(f, x, extension, handle_first, separate_integral, rewrite_complex, conds)
   1831     ans, i, b = integrate_primitive(fa, fd, DE)
   1832 elif case == 'base':
   1833     # XXX: We can't call ratint() directly here because it doesn't
   1834     # handle polynomials correctly.
-> 1835     ans = integrate(fa.as_expr()/fd.as_expr(), DE.x, risch=False)
   1836     b = False
   1837     i = S.Zero

File ~\anaconda3\lib\site-packages\sympy\integrals\integrals.py:1566, in integrate(meijerg, conds, risch, heurisch, manual, *args, **kwargs)
   1563 integral = Integral(*args, **kwargs)
   1565 if isinstance(integral, Integral):
-> 1566     return integral.doit(**doit_flags)
   1567 else:
   1568     new_args = [a.doit(**doit_flags) if isinstance(a, Integral) else a
   1569         for a in integral.args]

File ~\anaconda3\lib\site-packages\sympy\integrals\integrals.py:613, in Integral.doit(self, **hints)
    611     antideriv = None
    612 else:
--> 613     antideriv = self._eval_integral(
    614         function, xab[0], **eval_kwargs)
    615     if antideriv is None and meijerg is True:
    616         ret = try_meijerg(function, xab)

File ~\anaconda3\lib\site-packages\sympy\integrals\integrals.py:1041, in Integral._eval_integral(self, f, x, meijerg, risch, manual, heurisch, conds, final)
   1037 #        poly(x)
   1038 # g(x) = -------
   1039 #        poly(x)
   1040 if g.is_rational_function(x) and not (manual or meijerg or risch):
-> 1041     parts.append(coeff * ratint(g, x))
   1042     continue
   1044 if not (manual or meijerg or risch):
   1045     # g(x) = Mul(trig)

File ~\anaconda3\lib\site-packages\sympy\integrals\rationaltools.py:84, in ratint(f, x, **flags)
     81 else:
     82     t = symbol.as_dummy()
---> 84 L = ratint_logpart(r, Q, x, t)
     86 real = flags.get('real')
     88 if real is None:

File ~\anaconda3\lib\site-packages\sympy\integrals\rationaltools.py:229, in ratint_logpart(f, g, x, t)
    226 t = t or Dummy('t')
    227 a, b = g, f - g.diff()*Poly(t, x)
--> 229 res, R = resultant(a, b, includePRS=True)
    230 res = Poly(res, t, composite=False)
    232 assert res, "BUG: resultant(%s, %s) cannot be zero" % (a, b)

File ~\anaconda3\lib\site-packages\sympy\polys\polytools.py:5183, in resultant(f, g, includePRS, *gens, **args)
   5180     raise ComputationFailed('resultant', 2, exc)
   5182 if includePRS:
-> 5183     result, R = F.resultant(G, includePRS=includePRS)
   5184 else:
   5185     result = F.resultant(G)

File ~\anaconda3\lib\site-packages\sympy\polys\polytools.py:2692, in Poly.resultant(f, g, includePRS)
   2690 if hasattr(f.rep, 'resultant'):
   2691     if includePRS:
-> 2692         result, R = F.resultant(G, includePRS=includePRS)
   2693     else:
   2694         result = F.resultant(G)

File ~\anaconda3\lib\site-packages\sympy\polys\polyclasses.py:672, in DMP.resultant(f, g, includePRS)
    670 lev, dom, per, F, G = f.unify(g)
    671 if includePRS:
--> 672     res, R = dmp_resultant(F, G, lev, dom, includePRS=includePRS)
    673     return per(res, kill=True), list(map(per, R))
    674 return per(dmp_resultant(F, G, lev, dom), kill=True)

File ~\anaconda3\lib\site-packages\sympy\polys\euclidtools.py:787, in dmp_resultant(f, g, u, K, includePRS)
    770 """
    771 Computes resultant of two polynomials in `K[X]`.
    772 
   (...)
    784 
    785 """
    786 if not u:
--> 787     return dup_resultant(f, g, K, includePRS=includePRS)
    789 if includePRS:
    790     return dmp_prs_resultant(f, g, u, K)

File ~\anaconda3\lib\site-packages\sympy\polys\euclidtools.py:446, in dup_resultant(f, g, K, includePRS)
    432 """
    433 Computes resultant of two polynomials in `K[x]`.
    434 
   (...)
    443 
    444 """
    445 if includePRS:
--> 446     return dup_prs_resultant(f, g, K)
    447 return dup_prs_resultant(f, g, K)[0]

File ~\anaconda3\lib\site-packages\sympy\polys\euclidtools.py:423, in dup_prs_resultant(f, g, K)
    420 if not f or not g:
    421     return (K.zero, [])
--> 423 R, S = dup_inner_subresultants(f, g, K)
    425 if dup_degree(R[-1]) > 0:
    426     return (K.zero, R)

File ~\anaconda3\lib\site-packages\sympy\polys\euclidtools.py:373, in dup_inner_subresultants(f, g, K)
    369 f, g, m, d = g, h, k, m - k
    371 b = -lc * c**d
--> 373 h = dup_prem(f, g, K)
    374 h = dup_quo_ground(h, b, K)
    376 lc = dup_LC(g, K)

File ~\anaconda3\lib\site-packages\sympy\polys\densearith.py:1093, in dup_prem(f, g, K)
   1091         break
   1092     elif not (dr < _dr):
-> 1093         raise PolynomialDivisionFailed(f, g, K)
   1095 return dup_mul_ground(r, lc_g**N, K)

PolynomialDivisionFailed: couldn't reduce degree in a polynomial division algorithm when dividing [-0.01152*_t**2 - 1.98951966012828e-13*_t + 32310.4348874306, 0.000829440000000001*_t**2 + 1.86365873964328*_t - 2326.35131189501, 4.1140224e-5*_t**2 - 0.067091714627158*_t + 102.359457723381] by [-1.3759414272e-7*_t**3 - 3.45589442479755e-18*_t**2 - 0.482392208034546*_t + 7.13384906703141e-12, 4.95338913791998e-9*_t**3 - 1.60762482921009e-5*_t**2 + 0.017366119489244*_t - 56.3618244006186]. This can happen when it's not possible to detect zero in the coefficient domain. The domain of computation is RR[_t]. Zero detection is guaranteed in this coefficient domain. This may indicate a bug in SymPy or the domain is user defined and doesn't implement zero detection properly.

@oscarbenjamin
Copy link
Contributor

Thanks. Really it's better if you just strip out all the unrelated stuff though in which case your example is just this:

from sympy import *

x = symbols('x')
p = ((179.751035845223*x**2 - 12.9420745808561*x + 0.569451281557668)
        /(1.0*x**4 - 0.144*x**3 + 0.006336*x**2 - 8.2944e-5*x + 3.31776e-6))
integrate(p, x)

A simple workaround is to convert the floats to rational:

In [6]: nsimplify(p).integrate().n()
Out[6]: 
                         ⎛ 2     9  ⎞                          ⎛ 2   18x    18- 8.9031339031339e-14logx  + ─────⎟ + 8.9031339031339e-14logx  - ──── + ────⎟ + 3744.813246775415625⎠                          ⎝     125    3125⎠                  

      ⎛125x⎞                        ⎛125x9atan⎜─────⎟ + 3744.81324677547atan⎜───── - 3⎟
      ⎝  3  ⎠                        ⎝  3

@oscarbenjamin
Copy link
Contributor

The question is really if integrate should convert to rational internally to handle cases like this.

@jksuom
Copy link
Member

jksuom commented Jul 4, 2022

The long division of polynomials fails when the leading coefficient of a remainder is nonzero because of a rounding error. If f and g have leading coefficients a and b, then it is expected that a - b*(a/b) == 0. Otherwise the degree of the (partial) remainder is the same as the degree of f and this error will be raised. This can be fixed in the same way as here:

elif dr == _dr and not K.is_Exact:
# remove leading term created by rounding error
r = dup_strip(r[1:])
dr = dup_degree(r)
if dr < dg:
break

(There are other places in densearith.py where this could also be done.)

@oscarbenjamin
Copy link
Contributor

There are other places in densearith.py where this could also be done.

They all seem to follow dup_mul_term/dup_sub or dmp_mul_term/dmp_sub so maybe there could be a function for handling this combination:

def dup_sub_mul_strip(f, g, c, i, K):
    """Compute r = f - g*c*x**i where the leading term of f should cancel"""
    G = dup_mul_term(g, c, i, K)
    r = dup_sub(f, G, K)
    
    if not K.is_exact and dup_degree(r) == dup_degree(f):
        # remove leading term left over by rounding error
        r = dup_strip(r[1:])

    return r

What happens if the new leading term should also cancel though?

@jksuom
Copy link
Member

jksuom commented Jul 4, 2022

What happens if the new leading term should also cancel though?

That is probably not easy to detect. Maybe the dup/dmp methods should convert the coefficients for the computation.

@oscarbenjamin
Copy link
Contributor

Maybe dup_sub_mul_strip is a bit too complicated to understand. I guess just subs could be included:

def dup_sub_mul_strip(f, g, K):
    """Compute r = f - g where the leading terms should cancel"""
    r = dup_sub(f, g, K)
    
    if not K.is_exact and dup_degree(r) == dup_degree(f):
        # remove leading term left over by rounding error
        r = dup_strip(r[1:])

    return r

Maybe the dup/dmp methods should convert the coefficients for the computation.

I think conversion is better done at a higher level if it needs to be done. Probably stripping the leading term is the best that can be done if conversion is not used.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants