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.

Sign up for GitHub

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

Jump to bottom

Strange error in groebner_basis() #10340

Closed
sagetrac-sbulygin mannequin opened this issue Nov 26, 2010 · 9 comments
Closed

Strange error in groebner_basis() #10340

sagetrac-sbulygin mannequin opened this issue Nov 26, 2010 · 9 comments
Assignees
@sagetrac-mvngu
Labels
c: commutative algebra r: duplicate t: bug

Comments

@sagetrac-sbulygin
Copy link
Mannequin

sagetrac-sbulygin mannequin commented Nov 26, 2010

There is a ValueError occurring quite strangely when calling groebner_basis() for an ideal in BooleanPolynomialRing. Here is the example code

R.<Y0100, Y0101, Y0102, Y0103, Y0104, Y0105, Y0106, Y0107, Y0108, Y0109, Y0110, Y0111, Y0112, Y0113, Y0114, Y0115, Y0116, Y0117, Y0118, Y0119, Y0120, Y0121, Y0122, Y0123, Y0124, Y0125, Y0126, Y0127, Y0128, Y0129, Y0130, Y0131, Y0132, Y0133, Y0134, Y0135, Y0136, Y0137, Y0138, Y0139, Y0140, Y0141, Y0142, Y0143, Y0144, Y0145, Y0146, Y0147, X0100, X0101, X0102, X0103, X0104, X0105, X0106, X0107, X0108, X0109, X0110, X0111, X0112, X0113, X0114, X0115, X0116, X0117, X0118, X0119, X0120, X0121, X0122, X0123, X0124, X0125, X0126, X0127, X0128, X0129, X0130, X0131, X0132, X0133, X0134, X0135, X0136, X0137, X0138, X0139, X0140, X0141, X0142, X0143, X0144, X0145, X0146, X0147, K00, K01, K02, K03, K04, K05, K06, K07, K08, K09, K10, K11, K12, K13, K14, K15, K16, K17, K18, K19, K20, K21, K22, K23, K24, K25, K26, K27, K28, K29, K30, K31, K32, K33, K34, K35, K36, K37, K38, K39, K40, K41, K42, K43, K44, K45, K46, K47>=BooleanPolynomialRing(order="degrevlex")

I=ideal([X0100 + K00 + 1,
X0101 + K01,
X0102 + K02 + 1,
X0103 + K03 + 1,
X0104 + K04,
X0105 + K05 + 1,
X0106 + K06,
X0107 + K07 + 1,
X0108 + K08,
X0109 + K09 + 1,
X0110 + K10 + 1,
X0111 + K11 + 1,
X0112 + K12 + 1,
X0113 + K13,
X0114 + K14 + 1,
X0115 + K15 + 1,
X0116 + K16 + 1,
X0117 + K17,
X0118 + K18,
X0119 + K19 + 1,
X0120 + K20 + 1,
X0121 + K21 + 1,
X0122 + K22 + 1,
X0123 + K23 + 1,
X0124 + K24 + 1,
X0125 + K25 + 1,
X0126 + K26,
X0127 + K27 + 1,
X0128 + K28,
X0129 + K29,
X0130 + K30,
X0131 + K31 + 1,
X0132 + K32 + 1,
X0133 + K33,
X0134 + K34,
X0135 + K35 + 1,
X0136 + K36,
X0137 + K37 + 1,
X0138 + K38 + 1,
X0139 + K39,
X0140 + K40 + 1,
X0141 + K41,
X0142 + K42 + 1,
X0143 + K43,
X0144 + K44,
X0145 + K45,
X0146 + K46,
X0147 + K47,
X0132 + 1,
X0116 + 1,
X0100,
X0133,
X0117 + 1,
X0101,
X0134,
X0118 + 1,
X0102 + 1,
X0135,
X0119,
X0103 + 1,
X0136 + 1,
X0120,
X0104,
X0137,
X0121 + 1,
X0105,
X0138,
X0122,
X0106 + 1,
X0139,
X0123,
X0107,
X0140 + 1,
X0124,
X0108 + 1,
X0141 + 1,
X0125 + 1,
X0109,
X0142,
X0126,
X0110,
X0143 + 1,
X0127 + 1,
X0111,
X0144 + 1,
X0128 + 1,
X0112,
X0145,
X0129,
X0113,
X0146 + 1,
X0130 + 1,
X0114 + 1,
X0147 + 1,
X0131 + 1,
X0115
])

I.groebner_basis() # reports an error

the error being

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/<ipython console> in <module>()

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/sage/rings/polynomial/pbori.so in sage.rings.polynomial.pbori.BooleanPolynomialIdeal.groebner_basis (sage/rings/polynomial/pbori.cpp:25491)()

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in __call__(self, *args, **kwds)
    138         if heuristic:
    139             complete_dict=self.heuristicFunction(complete_dict)
--> 140         return self.f(**complete_dict)
    141     def __init__(self,f,heuristic_function):
    142         (self.argnames,self.varargs,self.varopts,self.defaults)=getargspec(f)

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in __call__(self, *args, **kwds)
    138         if heuristic:
    139             complete_dict=self.heuristicFunction(complete_dict)
--> 140         return self.f(**complete_dict)
    141     def __init__(self,f,heuristic_function):
    142         (self.argnames,self.varargs,self.varopts,self.defaults)=getargspec(f)

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    186                    
    187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
--> 188             I=f(I,**kwds)
    189             if option_set:
    190                 if post:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in wrapper(I, **kwds)
    185                        print "preprocessing for option:", option
    186                    
--> 187                    (I,state)=pre(**dict([(k,v) for (k,v) in locals().iteritems() if k in pre_args]))
    188             I=f(I,**kwds)
    189             if option_set:

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/gbcore.pyc in llfirst_pre(I, prot)
    223     
    224 def llfirst_pre(I,prot):
--> 225     (eliminated,llnf, I)=eliminate(I,on_the_fly=False,prot=prot)
    226     return (I,eliminated)
    227 

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/ll.pyc in eliminate(polys, on_the_fly, prot, reduction_function, optimized)
    109         reduction_function=reduction_function,
    110         reduce_ll_system=(not on_the_fly),
--> 111         prot=prot)
    112   else:
    113       reductors=ll_encode(linear_leads,reduce=(not on_the_fly),prot=prot)

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/ll.pyc in eliminate_ll_ranked(ll_system, to_reduce, reduction_function, reduce_ll_system, prot)
    146       return iter(Monomial(v).variables()).next().index()
    147   #sorted_var_indices=[var_index(v) for v in sorted_vars]
--> 148   to_ring=Ring(len(sorted_vars))
    149   map_back_indices = dict([(i, var_index(v)) for (i, v) in enumerate(sorted_vars)])
    150   map_from_indices = dict([(var_index(v), i) for (i, v) in enumerate(sorted_vars)])

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/polybori/PyPolyBoRi.pyc in Ring(n, order)
     17 
     18 def Ring(n, order='lp'):
---> 19     return BooleanPolynomialRing(n, 'x', order=order)
     20 
     21 BoolePolynomialVector = BooleanPolynomialVector

/home/sbulygin/Sage/sage-4.6-linux-32bit-ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-packages/sage/rings/polynomial/pbori.so in sage.rings.polynomial.pbori.BooleanPolynomialRing.__init__ (sage/rings/polynomial/pbori.cpp:4458)()

ValueError: Number of variables must be greater than 1.

Interestingly enough, the same ideal, but without the last generator gets through

I=ideal([X0100 + K00 + 1,
X0101 + K01,
X0102 + K02 + 1,
X0103 + K03 + 1,
X0104 + K04,
X0105 + K05 + 1,
X0106 + K06,
X0107 + K07 + 1,
X0108 + K08,
X0109 + K09 + 1,
X0110 + K10 + 1,
X0111 + K11 + 1,
X0112 + K12 + 1,
X0113 + K13,
X0114 + K14 + 1,
X0115 + K15 + 1,
X0116 + K16 + 1,
X0117 + K17,
X0118 + K18,
X0119 + K19 + 1,
X0120 + K20 + 1,
X0121 + K21 + 1,
X0122 + K22 + 1,
X0123 + K23 + 1,
X0124 + K24 + 1,
X0125 + K25 + 1,
X0126 + K26,
X0127 + K27 + 1,
X0128 + K28,
X0129 + K29,
X0130 + K30,
X0131 + K31 + 1,
X0132 + K32 + 1,
X0133 + K33,
X0134 + K34,
X0135 + K35 + 1,
X0136 + K36,
X0137 + K37 + 1,
X0138 + K38 + 1,
X0139 + K39,
X0140 + K40 + 1,
X0141 + K41,
X0142 + K42 + 1,
X0143 + K43,
X0144 + K44,
X0145 + K45,
X0146 + K46,
X0147 + K47,
X0132 + 1,
X0116 + 1,
X0100,
X0133,
X0117 + 1,
X0101,
X0134,
X0118 + 1,
X0102 + 1,
X0135,
X0119,
X0103 + 1,
X0136 + 1,
X0120,
X0104,
X0137,
X0121 + 1,
X0105,
X0138,
X0122,
X0106 + 1,
X0139,
X0123,
X0107,
X0140 + 1,
X0124,
X0108 + 1,
X0141 + 1,
X0125 + 1,
X0109,
X0142,
X0126,
X0110,
X0143 + 1,
X0127 + 1,
X0111,
X0144 + 1,
X0128 + 1,
X0112,
X0145,
X0129,
X0113,
X0146 + 1,
X0130 + 1,
X0114 + 1,
X0147 + 1,
X0131 + 1
])

I.groebner_basis() # works

the result being

[X0100, X0101, X0102 + 1, X0103 + 1, X0104, X0105, X0106 + 1, X0107, X0108 + 1, X0109, X0110, X0111, X0112, X0113, X0114 + 1, X0115 + K15 + 1, X0116 + 1, X0117 + 1, X0118 + 1, X0119, X0120, X0121 + 1, X0122, X0123, X0124, X0125 + 1, X0126, X0127 + 1, X0128 + 1, X0129, X0130 + 1, X0131 + 1, X0132 + 1, X0133, X0134, X0135, X0136 + 1, X0137, X0138, X0139, X0140 + 1, X0141 + 1, X0142, X0143 + 1, X0144 + 1, X0145, X0146 + 1, X0147 + 1, K00 + 1, K01, K02, K03, K04, K05 + 1, K06 + 1, K07 + 1, K08 + 1, K09 + 1, K10 + 1, K11 + 1, K12 + 1, K13, K14, K16, K17 + 1, K18 + 1, K19 + 1, K20 + 1, K21, K22 + 1, K23 + 1, K24 + 1, K25, K26, K27, K28 + 1, K29, K30 + 1, K31, K32, K33, K34, K35 + 1, K36 + 1, K37 + 1, K38 + 1, K39, K40, K41 + 1, K42 + 1, K43 + 1, K44 + 1, K45, K46 + 1, K47 + 1]

Duplicate of #12655

CC: @malb @sagetrac-PolyBoRi @alexanderdreyer

Component: commutative algebra

Keywords: groebner_basis, Boolean Polynomials

Reviewer: Alexander Dreyer

Issue created by migration from https://trac.sagemath.org/ticket/10340
@malb
Copy link
Member

malb commented Nov 26, 2010

Attachment: trac_10340_error_msg.patch.gz

@malb
Copy link
Member

malb commented Nov 26, 2010

comment:1

The error occurs because PolyBori -- when eliminating some variables from the system -- attempts to create a ring with zero variables. This also explains why your second system works.

I removed that check from our wrapper, but that doesn't only makes the code fail later. Michael, should PolyBoRi support rings with zero variables or not? In either case I think this is a bug in the upstream code.

In the process of looking into this I noticed that the error message was wrong. I fixed that in the attached patch.

PS: The author field is used to indicate who wrote the patch to fix the issue.

@malb
Copy link
Member

malb commented Nov 26, 2010

Changed author from Stas Bulygin to none

@malb
Copy link
Member

malb commented Mar 24, 2012

comment:3

This issue is fixed, I just tried it with 4.8. I suggest to close it.

@alexanderdreyer
Copy link
Mannequin

alexanderdreyer mannequin commented Mar 24, 2012

comment:4

Replying to @malb:

This issue is fixed, I just tried it with 4.8. I suggest to close it.

Indeed, that issue was resolved, for some reason the ticket got out of scope.

@alexanderdreyer

This comment has been minimized.

Sign in to view
@alexanderdreyer
Copy link
Mannequin

alexanderdreyer mannequin commented Jun 25, 2012

comment:5

Duplicate of #12655 (maybe even fixed earlier).
Abusing "positive review".

@alexanderdreyer

This comment has been minimized.

Sign in to view
@alexanderdreyer
Copy link
Mannequin

alexanderdreyer mannequin commented Jun 25, 2012

Reviewer: Alexander Dreyer

@jdemeyer jdemeyer closed this as completed Jul 4, 2012
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@sagetrac-mvngu sagetrac-mvngu

Labels
c: commutative algebra r: duplicate t: bug
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@malb @jdemeyer