Opened 10 years ago

Closed 10 years ago

# conversion problems in BooleanPolynomialRing with degrevlex order

Reported by: Owned by: Bouillaguet malb major sage-5.3 commutative algebra conversion malb, AlexanderDreyer, PolyBoRi sage-5.3.beta1 Alexander Dreyer, Charles Bouillaguet Martin Albrecht, Charles Bouillaguet N/A #13229

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
```

### comment:1 Changed 10 years ago by Bouillaguet

• Description modified (diff)

### comment:2 follow-up: ↓ 3 Changed 10 years ago by AlexanderDreyer

in `pbori.pyx`'s function `get_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).

### comment:3 in reply to: ↑ 2 ; follow-up: ↓ 5 Changed 10 years ago by Bouillaguet

in `pbori.pyx`'s function `get_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 Bouillaguet

• Authors set to Alexander Dreyer

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 AlexanderDreyer

in `pbori.pyx`'s function `get_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 malb

Re: Alexander, okay, let's try to fix it then :) Re: Charles, can you remove that `if True`?

### comment:7 Changed 10 years ago by Bouillaguet

• Status changed from new to needs_review

Done

### comment:8 follow-up: ↓ 9 Changed 10 years ago by malb

• Authors changed from Alexander Dreyer to Alexander Dreyer, Charles Bouillaguet
• 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 Bouillaguet

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 Bouillaguet

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"

Last edited 10 years ago by Bouillaguet (previous) (diff)

### comment:11 Changed 10 years ago by Bouillaguet

• Description modified (diff)

### comment:12 Changed 10 years ago by Bouillaguet

Apply pbori_degrevlex_problem.patch

### comment:13 in reply to: ↑ 10 Changed 10 years ago by AlexanderDreyer

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 AlexanderDreyer

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 Bouillaguet

includes first patch (dp_quickfix.patch) + add doctest

### comment:15 follow-up: ↓ 16 Changed 10 years ago by 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
• 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 AlexanderDreyer

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 AlexanderDreyer

• 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.)

### Changed 10 years ago by AlexanderDreyer

Indices obey variable reordering for DegRevLex?, introduces DegNegLex?

### comment:18 Changed 10 years ago by AlexanderDreyer

Apply pbori_consistent_degrevlex.patch

### comment:19 Changed 10 years ago by AlexanderDreyer

• Description modified (diff)

Rebased patch to Sage 5.2 rc0: Apply pbori_consistent_degrevlex_5-2.patch

Last edited 10 years ago by AlexanderDreyer (previous) (diff)

### Changed 10 years ago by AlexanderDreyer

Indices obey variable reordering for `DegRevLex`, introduces `DegNegLex` (rebased to Sage 5.2 rc0)

### comment:20 Changed 10 years ago by AlexanderDreyer

Apply pbori_consistent_degrevlex_5-2.patch

### comment:21 Changed 10 years ago by AlexanderDreyer

@Charles Bouillaguet: Does the new design (avoid internal index exposing to the user) fit your needs?

### comment:22 Changed 10 years ago by Bouillaguet

@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 malb

• 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 AlexanderDreyer

Nice to see that the refactored interface turns out to be useful!

### comment:25 Changed 10 years ago by jdemeyer

• Milestone changed from sage-5.2 to sage-5.3

### comment:26 Changed 10 years ago by jdemeyer

• Merged in set to sage-5.3.beta1
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.