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)

trac13849_deprecate_degrevlex.patch (10.7 KB) - added by malb 7 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 7 years ago by PolyBoRi

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.

comment:2 Changed 7 years ago by AlexanderDreyer

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: Changed 7 years ago by malb

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 AlexanderDreyer

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.

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

comment:5 Changed 7 years ago by PolyBoRi

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: Changed 7 years ago by 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).

comment:7 in reply to: ↑ 6 Changed 7 years ago by AlexanderDreyer

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 malb

  • Authors set to Martin Albrecht
  • Dependencies set to 13848

comment:9 Changed 7 years ago by malb

  • Dependencies changed from 13848 to #13848

comment:10 Changed 7 years ago by AlexanderDreyer

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 malb

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 PolyBoRi

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: Changed 7 years ago by 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?

comment:14 in reply to: ↑ 13 Changed 7 years ago by AlexanderDreyer

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 malb

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 malb

comment:16 Changed 7 years ago by malb

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

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

  • Milestone changed from sage-5.6 to sage-5.7

comment:19 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.7 to sage-pending

comment:20 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-pending to sage-5.13
  • Reviewers set to Alexander Dreyer

comment:21 Changed 6 years ago by jdemeyer

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