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

dup_count_complex_roots() can't handle degenerate cases #14738

Open
skirpichev opened this Issue May 23, 2018 · 1 comment

Comments

Projects
None yet
1 participant
@skirpichev
Contributor

skirpichev commented May 23, 2018

At least, if length of the real interval for the initial rectangle is zero:

In [4]: dup_count_complex_roots([1, 0, 1], ZZ, inf=(ZZ(0),ZZ(-1)), sup=(ZZ(0), ZZ(2)))
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-4-ea013456e06e> in <module>()
----> 1 dup_count_complex_roots([1, 0, 1], ZZ, inf=(ZZ(0),ZZ(-1)), sup=(ZZ(0), ZZ(2)))

~/src/sympy/sympy/polys/rootisolation.py in dup_count_complex_roots(f, K, inf, sup, exclude)
   1266     Q_L4 = _intervals_to_quadrants(I_L4, f1L4F, f2L4F, t, v, F)
   1267 
-> 1268     T = _traverse_quadrants(Q_L1, Q_L2, Q_L3, Q_L4, exclude=exclude)
   1269 
   1270     return _winding_number(T, F)

~/src/sympy/sympy/polys/rootisolation.py in _traverse_quadrants(Q_L1, Q_L2, Q_L3, Q_L4, exclude)
   1160                 rules.append((_rules_ambiguous[qq], corners[(j, i)]))
   1161             else:
-> 1162                 raise NotImplementedError("3 element rule (corner): " + str(qq))
   1163 
   1164         q1, k = Q[0], 1

NotImplementedError: 3 element rule (corner): ('OO', 'OO', 'A1')

The output should be 2, I think. Consider

In [6]: dup_count_complex_roots([1, 0, 1], ZZ, inf=(ZZ(0),ZZ(-1)), sup=(QQ(1, 100000), ZZ(2)))
Out[6]: 2

skirpichev added a commit to skirpichev/diofant that referenced this issue May 23, 2018

skirpichev added a commit to skirpichev/diofant that referenced this issue May 27, 2018

skirpichev added a commit to skirpichev/diofant that referenced this issue May 28, 2018

skirpichev added a commit to skirpichev/diofant that referenced this issue May 29, 2018

@skirpichev

This comment has been minimized.

Contributor

skirpichev commented May 31, 2018

Thinking more, I'm not sure if 2 is a correct output here.

According to the algorithm paper, it's important that roots which lie on the boundaries of adjacent rectangles be counted with exactly one rectangle. This condition is met by counting roots on the north edge, the east edge and on the north east corner.

I see two options how degenerate rectangles fit this picture. Either don't count roots on them or forbid such rectangles completely (raise an exception). Simple, but not too useful.

skirpichev added a commit to skirpichev/diofant that referenced this issue Jun 7, 2018

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