Opened 7 years ago
Closed 6 years ago
#13849 closed enhancement (fixed)
deprecate degrevlex when using PolyBoRi
Reported by: | malb | Owned by: | malb |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | commutative algebra | Keywords: | |
Cc: | PolyBoRi, AlexanderDreyer | Merged in: | sage-5.13.beta5 |
Authors: | Martin Albrecht | Reviewers: | Alexander Dreyer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13848 | Stopgaps: |
Description
PolyBoRi does not support the degrevlex term ordering, so !Sage emulates it by fiddling with the variable indices. This has produced subtle bugs over and over again. In light of this, "degrevlex" should be removed and replaced by a piece of documentation explaining how to emulate it by hand ("reverse your variables").
Attachments (1)
Change History (22)
comment:1 Changed 7 years ago by
comment:2 Changed 7 years ago by
We have now DegNegLex
(=dp_asc) in Sage, so one could use that instead (and of course reverse variables manually). But I have to look at the code again (unfortunately I'm already out of office for the holidays), since I think one can just switch to DegNegLex?, when calling polybori-code, an then switch back. I've done it somewhere else for a simliar bug.
comment:3 follow-up: ↓ 4 Changed 7 years ago by
Hi Alexander, so your vote is to attempt to fix it instead of dropping it?
comment:4 in reply to: ↑ 3 Changed 7 years ago by
Replying to malb:
Hi Alexander, so your vote is to attempt to fix it instead of dropping it?
Well, that had been my idea. #13202 should have fixed these issues, but I did not think about multi_polynomial_sequence.py. Of course, one could fix it here (by intraoducing a function to pboriy.pyx that wraps and dewraps DegRevLex
). But that would only fix this special issue. But since a user could call polybori's functions manually, I must admit that is not really a solution.
The correct solution would be to split pbori.pyx into polybori-interface (just reimplemention our upstream boost.python-based interface) and the implementation of BooleanPolynomial
, BooleanPolynomialRing
, etc.
But I guess we won't find the time for this on short notice. (It might me a good idea, if we switch to cython upstream. This might be happen, but also not on short notice.)
So, -langerredekurzersinn- finally deprecating DegRevLex
seem to be the best feasible way.
comment:5 Changed 7 years ago by
Hi!
I agree with the analysis of Alexander. That were my own thoughts except that I do not think that the best way really ends up best for the user (even if we had all time of the world).
I would like to add two more thoughts. I think we should really encourage users to have a look at all the tricks in PolyBoRi? and call PolyBoRi? functions directly when needed. In particular while the Sage docs feature a first class reference manual, our docs supplement it by profound advice on performance optimization.
Luckily Alexander repaired the typesetting of our docs. I really would have preferred him to enjoy his vacations, but since he repaired it, I would like to post the following link:
Given the following behaviour http://polybori.sourceforge.net/doc/tutorial/tutorialse2.html#x3-140002.1 any confusion about index order is really evil.
Michael
comment:6 follow-up: ↓ 7 Changed 7 years ago by
Alright, I'll deprecate the use of degrevlex in PolyBoRi then.
But I have to admit that I don't understand:
We have now DegNegLex (=dp_asc) in Sage, so one could use that instead (and of course reverse variables manually).
comment:7 in reply to: ↑ 6 Changed 7 years ago by
Replying to malb:
Alright, I'll deprecate the use of degrevlex in PolyBoRi then.
But I have to admit that I don't understand:
We have now DegNegLex (=dp_asc) in Sage, so one could use that instead (and of course reverse variables manually).
Before I added DegNegLex
, it had not been possible to emulate DegRevLex
by taking another ordering and revert the variable vector manually. This was just because that corresponding other ordering had not been there (for the user), yet. (So the automated reversion was done for allowing the user to access dp_asc
somehow, but it was error-prone, etc...)
Today, a Sage-user can just use DegNegLex
like a ipbori-user uses dp_asc
, so indeed the hacked DegRevLex
is not needed any more.
comment:8 Changed 7 years ago by
- Dependencies set to 13848
comment:9 Changed 7 years ago by
- Dependencies changed from 13848 to #13848
comment:10 Changed 7 years ago by
Around line 377:
deprecation(13849, "using 'degrevlex' in Boolean polynomial rings is deprecated. If needed, reverse the order of variables manually and use 'deglex'")
should read
...and use 'degneglex'")
Everything else looks fine.
comment:11 Changed 7 years ago by
Sorry if that reveals my ignorance, but I thought:
- deglex + inversed variable ordering == degrevlex
- degneglex == the other ordering besides deglex which PolyBoRi? supports
Is that wrong?
comment:12 Changed 7 years ago by
Martin, what you say is correct (unless you define degnexlex otherwise in some context I do not know). Degrevlex as in Singular corresponds to
1 1 1 0 0 -1 0 -1 0
or equivalenty, but redundant.
1 1 1 0 0 -1 0 -1 0 -1 0 0
So you see, it has to aspects (one negative and one from behind), the name might be considered as broken and irritating.
Negative lexicographical as in Singular (not a well ordering).
-1 0 0 0 -1 0 0 0 -1
As you can see degrevlex as in Singular is composed of the degree vector and negative lexicographical ordering (ls), but in reversed variable ordering.
deglex as in PolyBoRi? and in Singular (Dp with a big D)
1 1 1 1 0 0 0 1 0
dp_asc as in PolyBoRi? (degree reverse lexicographical ordering ascending)
1 1 1 -1 0 0 0 -1 0
So, the notion, degneglex can have it's benefits from systematic perspective as it's composed of the degree vector and the (non well ordering) negative lexicographical and indeed itself again a well ordering. From an unsystematical perspective, I just always added the ascending to the "degree reverse lexicographical" as it made sure it's the same order but twised
It's a simple ordering, but it is not equivalenty to degrevlex as in Singular and does not feature the nice theoretical properties for a certain class of systems (I've never come to the observation that that they apply in Boolean context).
While most people agree on these notions, here is no proper standardization on notions in computational algebra. I have indeed already seen some people define degree reverse lexicographical ordering to be the ordering PolyBoRi? calls dp_asc.
comment:13 follow-up: ↓ 14 Changed 7 years ago by
Hang on, that means then that the user should (a) reverse the variables and (b) choose degneglex to get degrevlex as defined in Singular?
comment:14 in reply to: ↑ 13 Changed 7 years ago by
Replying to malb:
Hang on, that means then that the user should (a) reverse the variables and (b) choose degneglex to get degrevlex as defined in Singular?
Yes, otherwise we would not had have to implemented dp_asc
(which was really hard). Have a look at pbori.pyx
. DegRevLex
is exactly implemented like this. (And DegNegLex
is Sage is exactly PolyBoRi
's dp_asc
.)
comment:15 Changed 7 years ago by
Dang, I've been ignorant the whole time! Thanks! I'll fix the patch accordingly and fix doctest failures etc.
Changed 7 years ago by
comment:16 Changed 7 years ago by
- Status changed from new to needs_review
Patch updated and doctests pass. Note this patch has a dependency chain.
comment:17 Changed 7 years ago by
- Status changed from needs_review to positive_review
Since we had discussed this thoroughly and the patch looks nice, I an give a positive review, proved that the patchbot succeeds.
comment:18 Changed 7 years ago by
- Milestone changed from sage-5.6 to sage-5.7
comment:19 Changed 7 years ago by
- Milestone changed from sage-5.7 to sage-pending
comment:20 Changed 6 years ago by
- Milestone changed from sage-pending to sage-5.13
- Reviewers set to Alexander Dreyer
comment:21 Changed 6 years ago by
- Merged in set to sage-5.13.beta5
- Resolution set to fixed
- Status changed from positive_review to closed
Of course I am biased, but I completely second the suggestion. I would like to give a little bit background. With ZDDs it's not possible to implement arbitrary monomial orderings efficiently. This is the reason why we have implemented only some orders which suffice for all most computations: lex., block, deglex, and degree reverse lexicographical ordering ascending. The ascending is there for a reason: It is exactly like degrevlex only that x_1<x_2. So, you have just to reverse variables (as malb explained) to get the same behaviour. Another aspect is that we deal in PolyBoRi? functions with ZDDs and suppose a certain behaviour. This might result in wrong results, slow behaviour or other errors.
It's unfortunate that it does not seem feasible to have a compatibility layer, but it's really difficult to have an interface that does both expose all power and flexibility of PolyBoRi? and at the same time pretends that there is no library with very specific structures under the interface.