Opened 10 years ago
Closed 10 years ago
#13202 closed defect (fixed)
conversion problems in BooleanPolynomialRing with degrevlex order
Reported by: | Bouillaguet | Owned by: | malb |
---|---|---|---|
Priority: | major | Milestone: | sage-5.3 |
Component: | commutative algebra | Keywords: | conversion |
Cc: | malb, AlexanderDreyer, PolyBoRi | Merged in: | sage-5.3.beta1 |
Authors: | Alexander Dreyer, Charles Bouillaguet | Reviewers: | Martin Albrecht, Charles Bouillaguet |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13229 | Stopgaps: |
Description (last modified by )
Some conversion between different BooleanPolynomial rings fail but they should not.
example :
sage: B.<a,b,c,d> = BooleanPolynomialRing(order='degrevlex') sage: P.<c,d> = BooleanPolynomialRing(order='lex') sage: P(B('c')) ERROR: An unexpected error occurred while tokenizing input The following traceback may be corrupted or invalid The error message is: ('EOF in multi-line statement', (1369, 0)) ....... TypeError: cannot convert polynomial c to Boolean PolynomialRing in c, d: name b not defined
Attachments (5)
Change History (31)
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 follow-up: ↓ 3 Changed 10 years ago by
Changed 10 years ago by
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 5 Changed 10 years ago by
Replying to AlexanderDreyer:
in
pbori.pyx
's functionget_var_mapping
, indices are used to represent the variables, but the reversing of the internal variable order is not obeyed here (PolyBoRi
does not support degrevlex directly, but a variant with revered variable order.). I attach a quick fix for that problem, but one can probably do better by using the the indexed reordering from the ring (I'm not so familiar with that part of pbori.pyx).
Wow ! Your patch seems to do it. I tried to patch the function myself but I couldn't. It would be great if some comments in the file explained what's going on. For instance, I somehow convinced myself that I wouldn't be able to solve the problem without accessing the pbind
array.
So, I discussed this off-list with malb, and we kind of agreed to deprecate degreglex for boolean polynomials (after all, it is exactly the same as deglex with variables in reverse order). How do you feel about this? I suppose that with your patch it is not necessary anymore...
comment:4 Changed 10 years ago by
I made a new patch that includes the first patch but adds a doctest that checks that everything goes well
comment:5 in reply to: ↑ 3 Changed 10 years ago by
Replying to Bouillaguet:
Replying to AlexanderDreyer:
in
pbori.pyx
's functionget_var_mapping
, indices are used to represent the variables, but the reversing of the internal variable order is not obeyed here (PolyBoRi
does not support degrevlex directly, but a variant with revered variable order.). I attach a quick fix for that problem, but one can probably do better by using the the indexed reordering from the ring (I'm not so familiar with that part of pbori.pyx).Wow ! Your patch seems to do it. I tried to patch the function myself but I couldn't. It would be great if some comments in the file explained what's going on. For instance, I somehow convinced myself that I wouldn't be able to solve the problem without accessing the
pbind
array.
I'll try to find some time to write some comments. (out out office and today)
So, I discussed this off-list with malb, and we kind of agreed to deprecate degreglex for boolean polynomials (after all, it is exactly the same as deglex with variables in reverse order). How do you feel about this? I suppose that with your patch it is not necessary anymore.
No,it's not the same! It's the same like a having PolyBoRi
's "dp_asc" with reversed indices.
But, there's no dp_asc in Sage. (Because we invented this in PolyBoRi
for technical reasons.)
degrevlex is necessary, because it's he most popular ordering in computational algebra, because it's the fastest for homogenous problem (and behaves well in others). So one cannot drop it.
comment:6 Changed 10 years ago by
Re: Alexander, okay, let's try to fix it then :)
Re: Charles, can you remove that if True
?
comment:8 follow-up: ↓ 9 Changed 10 years ago by
- Reviewers set to Martin Albrecht
Looks good, I'll let the patchbot decide whether doctests pass or not.
comment:9 in reply to: ↑ 8 Changed 10 years ago by
Replying to malb:
Looks good, I'll let the patchbot decide whether doctests pass or not.
For that to work, we would need to tell it to only apply the second patch. How do you do that ?
comment:10 follow-up: ↓ 13 Changed 10 years ago by
Still, there is something relatively annoying :
sage: R.<x,y,z> = BooleanPolynomialRing(order='degrevlex') sage: m = x # a random monomial sage: x.lm().index() # the index of the first variable of m, most people would expect "0" 2 sage: R.gen(2) z
And in fact, to make it shorter:
sage: R.gen(0) == R.gen( R.gen(0).lm().index() ) False
While this is not a bug in itself, it is disturbing, and it has caused at least one problem in my code. It also exposes to the user something that should be kept hidden from her (namely, how the sage interface implements the degrevlex ordering on top of polybori).
Fixing the .index() function to avoid this would in any case break Alexander's patch. If I understand correctly, his patch relies on this "feature"
comment:11 Changed 10 years ago by
- Description modified (diff)
comment:12 Changed 10 years ago by
Apply pbori_degrevlex_problem.patch
comment:13 in reply to: ↑ 10 Changed 10 years ago by
Fixing the .index() function to avoid this would in any case break Alexander's patch. If I understand correctly, his patch relies on this "feature"
Well, it would break much more since the the Sage uses pbori.pyx
also to interconnect betweento PolyBoRi
's python modules and its C++-based kernel (supplementing PolyBoRi
's original interface here). As long as Sage-only and PolyBoRi
-only function are not mixed, this should not be a problem.
But I just realized, that .variable()
is reordered (unlike .gen()
it shouldn't), so I'll check this for consistency.
comment:14 Changed 10 years ago by
I thought about this. For a clean fix, we will need to distinguish between pure dp_asc
and DegRevLex
. So I prepared a patch to add dp_asc
(as DegNegLex
) to Sage, see #13229.
BTW: Was the patchbot successful?
Changed 10 years ago by
comment:15 follow-up: ↓ 16 Changed 10 years ago by
So, I don't exactly understand what the plan is. The patch, even though it fixes the problem at the origin of this ticket, does not fixes all problems:
- m.index() exposes the hack behind the current implementation of degreglex
- Alexander seems to believe that there is a problem with variables()
So, do we want to remove the degrevlex from BooleanPolynomialRing? altogether, and instruct users to use the newly implemented degneglex instead, or do we want to actually support degrevlex? (and how?)
comment:16 in reply to: ↑ 15 Changed 10 years ago by
Replying to Bouillaguet:
So, I don't exactly understand what the plan is. The patch, even though it fixes the problem at the origin of this ticket, does not fixes all problems:
- m.index() exposes the hack behind the current implementation of degreglex
Yes, I'm about to fix that. (It's not only index to be fixed.)
- Alexander seems to believe that there is a problem with variables()
I thought ring.variable(i) should give the i-th polybori variable (not reordered). But thinking twice, that would cause more problems than it solves.
So, do we want to remove the degrevlex from BooleanPolynomialRing? altogether, and instruct users to use the newly implemented degneglex instead, or do we want to actually support degrevlex? (and how?)
The problem is the ambigious nature of pbori.pyx: On the one hand, it is the Sage implementation of BooleanPolynomial? which should support degrevlex in such a way, that the user is not aware of the reversed variables hack. On the other hand, Sage uses pbori.pyx as a lightweight alternative to polybori's original (boost-based) C++-to-python interface (for running polybori's highlevel library stuff in <python-site>/polybori/*). We don't need degrevlex here (but degneglex).
The latter is trivial, once DegNegLex
is in Sage. For the first point, I will provide a first variant later this day.
comment:17 Changed 10 years ago by
- Dependencies set to #13229
- Description modified (diff)
Here's my proposed change to pbori.pyx
.index()
, .iterindex()
and related functions obey the variable reordering in degrevlex now. Also, degneglex is supported now. Feel free to test it. (There are only a few degrevlex examples in the doctests, so some functionality might not be covered.)
comment:18 Changed 10 years ago by
Apply pbori_consistent_degrevlex.patch
comment:19 Changed 10 years ago by
- Description modified (diff)
Rebased patch to Sage 5.2 rc0: Apply pbori_consistent_degrevlex_5-2.patch
Changed 10 years ago by
Indices obey variable reordering for DegRevLex
, introduces DegNegLex
(rebased to Sage 5.2 rc0)
comment:20 Changed 10 years ago by
Apply pbori_consistent_degrevlex_5-2.patch
comment:21 Changed 10 years ago by
@Charles Bouillaguet: Does the new design (avoid internal index exposing to the user) fit your needs?
comment:22 Changed 10 years ago by
@AlexanderDreyer: I'm happy with it! It makes the patchbot happy so I suppose we could go for a positive review... malb?
comment:23 Changed 10 years ago by
- Reviewers changed from Martin Albrecht to Martin Albrecht, Charles Bouillaguet
- Status changed from needs_review to positive_review
Let's do it.
comment:24 Changed 10 years ago by
Nice to see that the refactored interface turns out to be useful!
comment:25 Changed 10 years ago by
- Milestone changed from sage-5.2 to sage-5.3
comment:26 Changed 10 years ago by
- Merged in set to sage-5.3.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
in
pbori.pyx
's functionget_var_mapping
, indices are used to represent the variables, but the reversing of the internal variable order is not obeyed here (PolyBoRi
does not support degrevlex directly, but a variant with revered variable order.). I attach a quick fix for that problem, but one can probably do better by using the the indexed reordering from the ring (I'm not so familiar with that part of pbori.pyx).