PolyBoRi monomial orders are wrong

[malb]

sage: P.<x,y> = PolynomialRing(GF(2),2,order='degrevlex')
sage: x > y
True

sage: P.<x,y> = BooleanPolynomialRing(2,order='degrevlex')
sage: x > y
False

This should be changed because it leads to funny performance figures.

CC: @malb

Component: commutative algebra

Keywords: polybori

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

[burcin]

Attachment: 2148-polybori_monomial_order_keywords.patch.gz

fix monomial order keywords in polybori wrapper

[burcin]

comment:1

attachment: 2148-polybori_monomial_order_keywords.patch corrects the monomial order keywords in the PolyBoRi wrapper.

[malb]

comment:2

I am not convinced the patch fixes the issue:

'dp' and 'Dp' refer to degrevlex and deglex respectively and in neither of those x < y.

sage: P.<x,y> = PolynomialRing(GF(2),order='degrevlex')
sage: x > y
True
sage: P.<x,y> = PolynomialRing(GF(2),order='deglex')
sage: x > y
True

However, there is a deglex with variables inverted ordering ib PolyBoRi which has no Singular/Sage equivalent AFAIK:

sage: B.<x,y> = BooleanPolynomialRing(2,order='deglex')
sage: x > y
True
sage: B.<x,y> = BooleanPolynomialRing(2,order='degrevlex')
sage: x > y
False

[burcin]

comment:3

You're right, it's not so simple. I'll look at it a bit more.

[burcin]

comment:4

On Wed, 20 Feb 2008 10:40:09 +0100
Alexander Dreyer <alexander.dreyer@itwm.fraunhofer.de> wrote:

> PolyBoRi does not implement degrevlex (dp), but a variant, which we
> called dp_asc. It is adp (not a dlex, as Martin states), but with
> variables reversed. The reason for this was, that this can be
> implemented more efficiently on our ZDD-based data structure. So, for
> correcting the command
> 
> B.<x,y> = BooleanPolynomialRing(2,order='degrevlex')
> 
> you have to reverse the variable vector before it is returned to <x, y>.
> (If there's something like BooleanVariable(idx), it has to be mapped to
> BooleVariable(n-idx).)

[burcin]

reverse variables for degrevlex to dp_asc conversion

[burcin]

comment:5

Attachment: 2148-polybori-fix_degrevlex.patch.gz

attachment: 2148-polybori-fix_degrevlex.patch arranges the variable indexes in the Sage - PolyBoRi interface to handle the difference between degrevlex and dp_asc orders.

Note that with this patch, printing is reversed when using dp_asc orders:

sage: P.<x,y,z> = BooleanPolynomialRing(3,order='degrevlex')
sage: x*y*z
z*y*x
sage: P.<x,y,z> = BooleanPolynomialRing(3,order='lex')
sage: x*y*z
x*y*z

[mwhansen]

comment:7

Looks good to me.

[sagetrac-mabshoff]

comment:8

Merged 2148-polybori-fix_degrevlex.patch in Sage 2.11.alpha0