Module: sage.rings.polynomial.term_order
Term Orderings
Sage supports the following term orderings:
sage: P.<x,y,z> = PolynomialRing(QQ,3,order='lex') sage: x > y True sage: x > y^2 True sage: x > 1 True sage: x^1*y^2 > y^3*z^4 True sage: x^3*y^2*z^4 < x^3*y^2*z^1 False
This term ordering is called 'lp' in Singular.
Let
then
or
and
sage: P.<x,y,z> = PolynomialRing(GF(127),3,order='degrevlex') sage: x > y True sage: x > y^2*z False sage: x > 1 True sage: x^1*y^5*z^2 > x^4*y^1*z^3 True sage: x^2*y*z^2 > x*y^3*z False
This term ordering is called 'dp' in Singular.
Let
then
or
and
sage: P.<x,y,z> = PolynomialRing(GF(2^8,'a'),3,order='deglex') sage: x > y True sage: x > y^2*z False sage: x > 1 True sage: x^1*y^2*z^3 > x^3*y^2*z^0 True sage: x^2*y*z^2 > x*y^3*z True
This term order is called 'Dp' in Singular.
sage: P.<x,y,z> = PolynomialRing(GF(127),3,order='invlex') sage: x > y False sage: y > x^2 True sage: x > 1 True sage: x*y > z False
This term ordering only makes sense in a non-commutative setting
because if P is the ring
and term ordering
'invlex' then it is equivalent to the ring
with
term ordering 'lex'.
This ordering is called 'rp' in Singular.
sage: P.<x,y,z> = PolynomialRing(QQ,3,order='neglex') sage: x > y False sage: x > 1 False sage: x^1*y^2 > y^3*z^4 False sage: x^3*y^2*z^4 < x^3*y^2*z^1 True sage: x*y > z False
This term ordering is called 'ls' in Singular.
Let
then
or
and
sage: P.<x,y,z> = PolynomialRing(QQ,3,order='negdegrevlex') sage: x > y True sage: x > x^2 True sage: x > 1 False sage: x^1*y^2 > y^3*z^4 True sage: x^2*y*z^2 > x*y^3*z False
This term ordering is called 'ds' in Singular.
Let
then
or
and
sage: P.<x,y,z> = PolynomialRing(QQ,3,order='negdeglex') sage: x > y True sage: x > x^2 True sage: x > 1 False sage: x^1*y^2 > y^3*z^4 True sage: x^2*y*z^2 > x*y^3*z True
This term ordering is called 'Ds' in Singular.
Of these, only 'degrevlex', 'deglex', 'invlex' and 'lex' are global orderings.
Additionally all these monomial orderings may be combined to product or block orderings, defined as:
Let
and
be
two ordered sets of variables,
a monomial ordering on
and
a monomial ordering on
.
The product ordering (or block ordering)
on
is defined as:
or
.
These block orderings are constructed in Sage by giving a comma separated list of monomial orderings with the length of each block attached to them.
As an example, consider constructing a block ordering where the first four variables are compared using the degree reverse lexicographical ordering while the last two variables in the second block are compared using negative lexicographical ordering.
sage: P.<a,b,c,d,e,f> = PolynomialRing(GF(127),6,order='degrevlex(4),neglex(2)') sage: a > c^4 False sage: a > e^4 True sage: e > f^2 False
The same result can be achieved by:
sage: T1 = TermOrder('degrevlex',4) sage: T2 = TermOrder('neglex',2) sage: T = T1 + T2 sage: P.<a,b,c,d,e,f> = PolynomialRing(GF(127),6,order=T) sage: a > c^4 False sage: a > e^4 True
If any other unsupported term ordering is given the provided string is passed through as is to SINGULAR, MACAULAY2, and MAGMA. This ensures that it is for example possible to calculated a Groebner basis with respect to some term ordering SINGULAR supports but Sage doesn't. However a warning is issued to make the user aware of the situation and potential typos:
sage: P.<a,b,c,d,e,f> = PolynomialRing(GF(127),6,order=T) sage: a > c^4 False sage: a > e^4 True
If any other unsupported term ordering is given the provided string is passed through as is to SINGULAR, MACAULAY2, and MAGMA. This ensures that it is for example possible to calculated a Groebner basis with respect to some term ordering SINGULAR supports but Sage doesn't. However a warning is issued to make the user aware of the situation and potential typos:
sage: T = TermOrder("royalorder") verbose 0 (...: term_order.py, __init__) Term ordering 'royalorder' unknown.
Author Log:
Class: TermOrder
See sage.rings.polynomial.term_order
for details on
supported term orderings.
self, [name=lex], [n=0], [blocks=True]) |
Construct a new term ordering object.
Input:
See the sage.rings.polynomial.term_order
module for
help which names and orderings are available.
sage: t = TermOrder('lex') sage: t Lexicographic term order sage: loads(dumps(t)) == t True
We can construct block orderings directly as
sage: TermOrder('degrevlex(3),neglex(2)') degrevlex(3),neglex(2) term order
or by adding together the blocks:
sage: t1 = TermOrder('degrevlex',3) sage: t2 = TermOrder('neglex',2) sage: t1 + t2 degrevlex(3),neglex(2) term order sage: t2 + t1 neglex(2),degrevlex(3) term order
NOTE: The optional
parameter is not necessary if only
non-block orderings like
are constructed. However, it
is useful if block orderings are to be constructed from this
TermOrder
object later.
Functions: compare_tuples_block,
compare_tuples_dp,
compare_tuples_Dp,
compare_tuples_ds,
compare_tuples_Ds,
compare_tuples_lp,
compare_tuples_ls,
compare_tuples_rp,
greater_tuple_block,
greater_tuple_Dp,
greater_tuple_dp,
greater_tuple_Ds,
greater_tuple_ds,
greater_tuple_lp,
greater_tuple_ls,
greater_tuple_rp,
is_global,
is_local,
macaulay2_str,
magma_str,
name,
singular_str
self, f, g) |
Compares two exponent tuple with respec to the block ordering as specified when constructing this element.
Input:
sage: P.<a,b,c,d,e,f>=PolynomialRing(ZZ,6, order='degrevlex(3),degrevlex(3)') sage: a > c^4 # indirect doctest False sage: a > e^4 True
self, f, g) |
Compares two exponent tuples with respect to the degree reversed lexicographical term order.
Input:
sage: P.<x,y> = PolynomialRing(GF(127),2,order='degrevlex') sage: x > y^2 # indirect doctest False sage: x > 1 True
self, f, g) |
Compares two exponent tuples with respect to the degree lexicographical term order.
Input:
sage: P.<x,y> = PolynomialRing(GF(127),2,order='deglex') sage: x > y^2 # indirect doctest False sage: x > 1 True
self, f, g) |
Compares two exponent tuples with respect to the negative degree reverse lexicographical term order.
Input:
sage: P.<x,y> = PolynomialRing(IntegerModRing(10), 2,order='negdegrevlex') sage: x > y^2 # indirect doctest True sage: x > 1 False
self, f, g) |
Compares two exponent tuples with respect to the negative degree lexicographical term order.
Input:
sage: P.<x,y> = PolynomialRing(GF(2), 2,order='negdeglex') sage: x > y^2 # indirect doctest True sage: x > 1 False
self, f, g) |
Compares two exponent tuples with respect to the lexicographical term order.
Input:
sage: P.<x,y> = PolynomialRing(QQ,2,order='lex') sage: x > y^2 # indirect doctest True sage: x > 1 True
self, f, g) |
Compares two exponent tuples with respect to the negative lexicographical term order.
Input:
sage: P.<x,y> = PolynomialRing(GF(2^8,'a'),2,order='neglex') sage: x > y^2 # indirect doctest False sage: x > 1 False
self, f, g) |
Compares two exponent tuples with respect to the inversed lexicographical term order.
Input:
sage: P.<x,y> = PolynomialRing(ZZ,2,order='invlex') sage: x > y^2 # indirect doctest False sage: x > 1 True
self, f, g) |
Compares two exponent tuple with respec to the block ordering as specified when constructing this element.
This method is called by the lm/lc/lt methods of MPolynomial_polydict
.
Input:
sage: P.<a,b,c,d,e,f>=PolynomialRing(ZZ,6, order='degrevlex(3),degrevlex(3)') sage: f = a + c^4; f.lm() # indirect doctest c^4 sage: g = a + e^4; g.lm() a
self, f, g) |
Returns the greater exponent tuple with respect to the total degree lexicographical term order.
Input:
sage: P.<x,y,z> = PolynomialRing(ZZ, 3, order='deglex') sage: f = x + y; f.lm() # indirect doctest x sage: f = x + y^2*z; f.lm() y^2*z
This method is called by the lm/lc/lt methods of
MPolynomial_polydict
.
self, f, g) |
Returns the greater exponent tuple with respect to the total degree reversed lexicographical term order.
Input:
sage: P.<x,y,z> = PolynomialRing(ZZ, 3, order='degrevlex') sage: f = x + y; f.lm() # indirect doctest x sage: f = x + y^2*z; f.lm() y^2*z
This method is called by the lm/lc/lt methods of
MPolynomial_polydict
.
self, f, g) |
Returns the greater exponent tuple with respect to the negative degree lexicographical term order.
Input:
sage: P.<x,y,z> = PolynomialRing(ZZ,3,order='negdeglex') sage: f = x + y; f.lm() # indirect doctest y sage: f = x + x^2; f.lm() x sage: f = x^2*y*z^2 + x*y^3*z; f.lm() x*y^3*z
This method is called by the lm/lc/lt methods of
MPolynomial_polydict
.
self, f, g) |
Returns the greater exponent tuple with respect to the negative degree reverse lexicographical term order.
Input:
sage: P.<x,y,z> = PolynomialRing(ZZ,3,order='negdegrevlex') sage: f = x + y; f.lm() # indirect doctest y sage: f = x + x^2; f.lm() x sage: f = x^2*y*z^2 + x*y^3*z; f.lm() x^2*y*z^2
This method is called by the lm/lc/lt methods of
MPolynomial_polydict
.
self, f, g) |
Returns the greater exponent tuple with respect to the lexicographical term order.
Input:
sage: P.<x,y,z> = PolynomialRing(ZZ,3,order='lex') sage: f = x + y^2; f.lm() # indirect doctest x
This method is called by the lm/lc/lt methods of
MPolynomial_polydict
.
self, f, g) |
Returns the greater exponent tuple with respect to the negative lexicographical term order.
This method is called by the lm/lc/lt methods of
MPolynomial_polydict
.
Input:
sage: P.<a,b,c,d,e,f>=PolynomialRing(ZZ,6, order='degrevlex(3),degrevlex(3)') sage: f = a + c^4; f.lm() # indirect doctest c^4 sage: g = a + e^4; g.lm() a
self, f, g) |
Returns the greater exponent tuple with respect to the inversed lexicographical term order.
Input:
sage: P.<x,y,z> = PolynomialRing(ZZ,3,order='invlex') sage: f = x + y; f.lm() # indirect doctest y sage: f = y + x^2; f.lm() y
This method is called by the lm/lc/lt methods of
MPolynomial_polydict
.
self) |
Return True
if this term ordering is definitely
global. Return False
otherwise, which includes unknown
term orderings.
sage: T = TermOrder('lex') sage: T.is_global() True sage: T = TermOrder('degrevlex', 3) + TermOrder('degrevlex', 3) sage: T.is_global() True sage: T = TermOrder('degrevlex', 3) + TermOrder('negdegrevlex', 3) sage: T.is_global() False
self) |
Return True
if this term ordering is definitely
local. Return False
otherwise, which includes unknown
term orderings.
sage: T = TermOrder('lex') sage: T.is_local() False sage: T = TermOrder('negdeglex', 3) + TermOrder('negdegrevlex', 3) sage: T.is_local() True sage: T = TermOrder('degrevlex', 3) + TermOrder('negdegrevlex', 3) sage: T.is_local() False
self) |
Return a Macaulay2 representation of self.
Used to convert polynomial rings to their Macaulay2 representation.
sage: P = PolynomialRing(GF(127),8,names='x',order='degrevlex(3),lex(5)') sage: T = P.term_order() sage: T.macaulay2_str() '(GRevLex => 3,Lex => 5)' sage: P._macaulay2_() # optional -- requires macaulay2 ZZ/127 [x0, x1, x2, x3, x4, x5, x6, x7, MonomialOrder => {GRevLex => 3, Lex => 5}, MonomialSize => 16]
self) |
Return a MAGMA representation of self.
Used to convert polynomial rings to their MAGMA representation.
sage: P = PolynomialRing(GF(127),10,names='x',order='degrevlex') sage: P._magma_() # optional, requires MAGMA Polynomial ring of rank 10 over GF(127) Graded Reverse Lexicographical Order Variables: x0, x1, x2, x3, x4, x5, x6, x7, x8, x9
sage: T = P.term_order() sage: T.magma_str() '"grevlex"'
self) |
sage: TermOrder('lex').name() 'lex'
self) |
Return a SINGULAR representation of self.
Used to convert polynomial rings to their SINGULAR representation.
sage: P = PolynomialRing(GF(127),10,names='x',order='lex(3),deglex(5),lex(2)') sage: T = P.term_order() sage: T.singular_str() '(lp(3),Dp(5),lp(2))' sage: P._singular_() // characteristic : 127 // number of vars : 10 // block 1 : ordering lp // : names x0 x1 x2 // block 2 : ordering Dp // : names x3 x4 x5 x6 x7 // block 3 : ordering lp // : names x8 x9 // block 4 : ordering C
Special Functions: __add__,
__cmp__,
__getitem__,
__init__,
__iter__,
__len__,
_repr_
self, other) |
Block ordering constructor.
Input:
sage: from sage.rings.polynomial.term_order import TermOrder sage: TermOrder('deglex',2) + TermOrder('degrevlex(3),neglex(3)') deglex(2),degrevlex(3),neglex(3) term order
self, other) |
Only equality testing makes sense here.
sage: TermOrder('lex') == TermOrder('lex',3) True
sage: TermOrder('degrevlex') == TermOrder('lex') False
sage: T1 = TermOrder('lex',2)+TermOrder('lex',3) sage: T2 = TermOrder('lex',3)+TermOrder('lex',2) sage: T1 == T2 False
sage: T1 = TermOrder('lex',2)+TermOrder('neglex',3) sage: T2 = TermOrder('lex',2)+TermOrder('neglex',3) sage: T1 == T2 True
self, i) |
Return the i-th block of this term ordering.
Input:
sage: T = TermOrder('lex') sage: T[0] Lexicographic term order
sage: T = TermOrder('lex', 2) + TermOrder('degrevlex', 3) sage: T[1] Degree reverse lexicographic term order
Note that len(self)
does not count blocks but variables.
sage: T = TermOrder('lex', 2) + TermOrder('degrevlex', 3) sage: T[len(T)-1] Traceback (most recent call last): ... IndexError: tuple index out of range
self) |
Iterate over the blocks of this term ordering.
sage: T = TermOrder('lex') sage: list(T) # indirect doctest [Lexicographic term order]
sage: T = TermOrder('lex', 2) + TermOrder('degrevlex', 3) sage: list(T) [Lexicographic term order, Degree reverse lexicographic term order]
Note that len(self)
and len(list(self))
are not
the same. The former counts the number of variables in
self
while the latter counts the number of blocks.
self) |
Return the length of this term ordering, i.e. the number of variables it covers. This may be zero for undefinitely many variables.
sage: T = TermOrder('lex') sage: len(T) 0 sage: T = TermOrder('lex', 2) + TermOrder('degrevlex', 3) sage: len(T) 5
self) |
sage: TermOrder('lex') # indirect doctest Lexicographic term order