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:

Status badges

Description (last modified by AlexanderDreyer)

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)

dp_quickfix.patch (971 bytes) - added by AlexanderDreyer 10 years ago.
pbori_degrevlex_problem.2.patch (2.1 KB) - added by Bouillaguet 10 years ago.
pbori_degrevlex_problem.patch (2.1 KB) - added by Bouillaguet 10 years ago.
includes first patch (dp_quickfix.patch) + add doctest
pbori_consistent_degrevlex.patch (18.2 KB) - added by AlexanderDreyer 10 years ago.
Indices obey variable reordering for DegRevLex?, introduces DegNegLex?
pbori_consistent_degrevlex_5-2.patch (18.1 KB) - added by AlexanderDreyer 10 years ago.
Indices obey variable reordering for DegRevLex, introduces DegNegLex (rebased to Sage 5.2 rc0)

Download all attachments as: .zip

Change History (31)

comment:1 Changed 10 years ago by Bouillaguet

  • Description modified (diff)

comment:2 follow-up: 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).

Changed 10 years ago by AlexanderDreyer

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

Replying to 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.

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

Replying to Bouillaguet:

Replying to 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: 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

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

Changed 10 years ago by Bouillaguet

includes first patch (dp_quickfix.patch) + add doctest

comment:15 follow-up: 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

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