polybori / gb computation / set error

[cbwolf]

Hello,

There is a problem with polybori in sage-5.0.beta11. It crashes with the following error message:

Traceback (most recent call last):
  File "indexingError.py", line 13, in <module>
    B = I.groebner_basis()  # maximal degree 2 extension
  File "pbori.pyx", line 4853, in sage.rings.polynomial.pbori.BooleanPolynomialIdeal.groebner_basis (sage/rings/polynomial/pbori.cpp:28211)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 149, in __call__
    return self.f(**complete_dict)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 149, in __call__
    return self.f(**complete_dict)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 199, in wrapper
    I=f(I,**kwds)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 149, in __call__
    return self.f(**complete_dict)
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 198, in wrapper
    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
  File "/opt/software/sage-5.0.beta11/local/lib/python2.7/site-packages/polybori/gbcore.py", line 323, in other_ordering_pre
    old_ring=I[0].ring()
TypeError: 'set' object does not support indexing

The error can be consistently created with the following sage code:

# problem, if only a part of the variables appears in the problem

# slightly too large ring
pR.<s0s0, s0s1, s0s2, s0s3, s0s4, s0s5, s0s6, s0s7, s1s0, s1s1, s1s2, s1s3, s1s4, s1s5, s1s6, s1s7, s2s0, s2s1, s2s2, s2s3, s3s0, s3s1, s3s2, s3s3> = BooleanPolynomialRing()

# a problem instance
problem = [s1s0*s1s1, s0s0*s0s1 + s0s0 + s0s1 + s2s0 + s3s0*s3s1 + s3s0 + s3s1, s1s1 + s2s0 + s3s0 + s3s1 + 1, s0s0*s0s1 + s1s1 + s3s0*s3s1 + s3s0, s0s1 + s1s0 + s1s1 + s3s0, s0s0*s0s1 + s0s0 + s0s1 + s1s1 + s2s0 + s3s1, s0s1 + s1s0, s0s0*s0s1 + s0s0 + s0s1 + s1s0 + s2s0 + s3s1, s0s0 + s2s0 + s3s0*s3s1 + s3s0 + 1, s0s0 + s1s1]

# try to solve via Groebner
I = ideal(problem)
B = I.groebner_basis() # crashes exactly here
print B

I guess it's a problem when converting the result back from polybori to Sage.

I use sage 5.0-beta11 on a 64 bit machine, namely

• AMD Opteron(TM) Processor 6276 @ 2.3 GHz
• Linux 2.6.32-220.2.1.el6.x86_64

sage 5.0 was built directly from the sources.

Best, Christopher

[Bouillaguet]

This does not crash for me, in Sage 5.5.

[Bouillaguet]

doctest to make sure it does not happen again

[AlexanderDreyer]

The patch makes sense and looks fine, so positive review.

[PolyBoRi]

well, it's quite mysterious where the set came from in the crashing... I looked at the code, and it uses sets with much caution.

By the way, for most PolyBoRi? code, you can use an immense number of extra variables and it will not affect performance too much.

[AlexanderDreyer]

The set probably arises from eliminate_identical_variables. This issue was fixed some time ago for polybori 0.8.2, see:  https://bitbucket.org/brickenstein/polybori/commits/f247a53 .

[jdemeyer]

If the patch needs to be merged, the milestone should be an actual Sage release.

Otherwise, I might close the ticket without merging the patch.