deprecate degrevlex when using PolyBoRi

[malb]

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

Depends on #13848

CC: @sagetrac-PolyBoRi @alexanderdreyer

Component: commutative algebra

Author: Martin Albrecht

Reviewer: Alexander Dreyer

Merged: sage-5.13.beta5

Issue created by migration from https://trac.sagemath.org/ticket/13849

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:1

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.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:2

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.

[malb]

comment:3

Hi Alexander, so your vote is to attempt to fix it instead of dropping it?

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:4

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.

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:5

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

[malb]

comment:6

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:7

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.

[malb]

Dependencies: 13848

[malb]

Author: Martin Albrecht

[malb]

Changed dependencies from 13848 to #13848

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:10

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.

[malb]

comment:11

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?

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:12

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.

[malb]

comment:13

Hang on, that means then that the user should (a) reverse the variables and (b) choose degneglex to get degrevlex as defined in Singular?

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:14

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

[malb]

comment:15

Dang, I've been ignorant the whole time! Thanks! I'll fix the patch accordingly and fix doctest failures etc.

[malb]

Attachment: trac13849_deprecate_degrevlex.patch.gz

[malb]

comment:16

Patch updated and doctests pass. Note this patch has a dependency chain.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:17

Since we had discussed this thoroughly and the patch looks nice, I an give a positive review, proved that the patchbot succeeds.

[jdemeyer]

Reviewer: Alexander Dreyer

[jdemeyer]

Merged: sage-5.13.beta5