Home       Trees       Indices       Help   
Package sage :: Package rings :: Package polynomial :: Module term_order
[hide private]
[frames] | no frames]

Module term_order

source code


Term Orderings

\SAGE supports the following term orderings:

\begin{description}
\item[Lexicographic (\emph{lex})]

$x^a < x^b \Leftrightarrow \exists\; 0 \le i < n : a_0 = b_0, \ldots, a_{i-1} = b_{i-1}, a_i < b_i$

EXAMPLES:
    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.

\item[Degree reverse lexicographic (\emph{degrevlex})]

Let $deg(x^a) = a_0 + \cdots + a_{n-1},$ then
$x^a < x^b \Leftrightarrow deg(x^a) < deg(x^b)$ or
$deg(x^a) = deg(x^b)$ and $\exists\ 0 \le i < n: a_{n-1} = b_{n-1}, \ldots, a_{i+1} = b_{i+1}, a_i > b_i.$

EXAMPLES:
    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.

\item[Degree lexicographic (\emph{deglex})]

Let $deg(x^a) = a_0 + \cdots + a_{n-1},$ then
$x^a < x^b \Leftrightarrow deg(x^a) < deg(x^b)$ or
$deg(x^a) = deg(x^b)$ and $\exists\ 0 \le i < n:a_0 = b_0, \ldots, a_{i-1} = b_{i-1}, a_i < b_i.$

EXAMPLES:
    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.

\item[Inverse lexicographic (\emph{invlex})]

$x^a < x^b \Leftrightarrow \exists\; 0 \le i < n : a_{n-1} = b_{n-1}, \ldots, a_{i+1} = b_{i+1}, a_i < b_i.$

EXAMPLES:
    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 $k[x_1, \dots, x_n]$ and term ordering
'invlex' then it is equivalent to the ring $k[x_n, \dots, x_1]$ with
term ordering 'lex'. 

This ordering is called 'rp' in Singular.

\item[Negative lexicographic (\emph{neglex})]

$x^a < x^b \Leftrightarrow \exists\; 0 \le i < n : a_0 = b_0, \ldots, a_{i-1} = b_{i-1}, a_i > b_i$

EXAMPLES:
    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.

\item[Negative degree reverse lexicographic (\emph{negdegrevlex})]

Let $deg(x^a) = a_0 + \cdots + a_{n-1},$ then
$x^a < x^b \Leftrightarrow deg(x^a) > deg(x^b)$ or
$deg(x^a) = deg(x^b)$ and $\exists\ 0 \le i < n: a_{n-1} = b_{n-1}, \ldots, a_{i+1} = b_{i+1}, a_i > b_i.$

EXAMPLES:
    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.

\item[Negative degree lexicographic (\emph{negdeglex})]

Let $deg(x^a) = a_0 + \cdots + a_{n-1},$ then
$x^a < x^b \Leftrightarrow deg(x^a) > deg(x^b)$ or
$deg(x^a) = deg(x^b)$ and $\exists\ 0 \le i < n: a_0 = b_0, \ldots, a_{i-1} = b_{i-1}, a_i < b_i.$

EXAMPLES:
    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.

\end{description}

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 $x = (x_0, \ldots, x_{n-1})$ and $y = (y_0, \ldots, y_{m-1})$ be
two ordered sets of variables, $<_1$ a monomial ordering on $k[x]$ and
$<_2$ a monomial ordering on $k[y]$.

The product ordering (or block ordering) $<\ := (<_1,<_2)$ on $k[x,y]$
is defined as: $x^a y^b < x^A y^B \Leftrightarrow x^a <_1 x^A$ or
$(x^a =x^A \textrm{ and } y^b <_2 y^B)$.

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.

EXAMPLE:

   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, \textsc{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, \textsc{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.

AUTHORS:
    -- David Joyner and William Stein: initial version multi_polynomial_ring
    -- Kiran S. Kedlaya: added macaulay2 interface
    -- Martin Albrecht: implemented native term orderings, refactoring


Classes [hide private]
  TermOrder
A term order.
Variables [hide private]
  print_name_mapping = {'deglex': 'Degree lexicographic', 'degre...
  singular_name_mapping = {'deglex': 'Dp', 'degrevlex': 'dp', 'i...
  macaulay2_name_mapping = {'deglex': 'GLex', 'degrevlex': 'GRev...
  magma_name_mapping = {'deglex': '"glex"', 'degrevlex': '"grevl...
  inv_singular_name_mapping = {'Dp': 'deglex', 'Ds': 'negdeglex'...
  lp_description = '\nLexicographic (lex) term ordering.\n\n$x^a...
  dp_description = '\nDegree reverse lexicographic (degrevlex) t...
  Dp_description = '\nDegree lexicographic (deglex) term orderin...
  rp_description = '\nInverse lexicographic (invlex) term orderi...
  ls_description = '\nNegative lexicographic (neglex) term order...
  ds_description = '\nNegative degree reverse lexicographic (neg...
  Ds_description = '\nNegative degree lexicographic (negdeglex) ...
  description_mapping = {'Dp': '\nDegree lexicographic (deglex) ...
Variables Details [hide private]

print_name_mapping

Value:
{'deglex': 'Degree lexicographic',
 'degrevlex': 'Degree reverse lexicographic',
 'invlex': 'Inverse Lexicographic',
 'lex': 'Lexicographic',
 'negdeglex': 'Negative degree lexicographic',
 'negdegrevlex': 'Negative degree reverse lexicographic',
 'neglex': 'Negative lexicographic'}

singular_name_mapping

Value:
{'deglex': 'Dp',
 'degrevlex': 'dp',
 'invlex': 'rp',
 'lex': 'lp',
 'negdeglex': 'Ds',
 'negdegrevlex': 'ds',
 'neglex': 'ls'}

macaulay2_name_mapping

Value:
{'deglex': 'GLex',
 'degrevlex': 'GRevLex',
 'lex': 'Lex',
 'revlex': 'RevLex, Global=>false'}

magma_name_mapping

Value:
{'deglex': '"glex"', 'degrevlex': '"grevlex"', 'lex': '"lex"'}

inv_singular_name_mapping

Value:
{'Dp': 'deglex',
 'Ds': 'negdeglex',
 'dp': 'degrevlex',
 'ds': 'negdegrevlex',
 'lp': 'lex',
 'ls': 'neglex',
 'rp': 'invlex'}

lp_description

Value:
'''
Lexicographic (lex) term ordering.

$x^a < x^b <=> \\exists\\; 0 <= i < n : a_0 = b_0, ..., a_{i-1} = b_{i\
-1}, a_i < b_i$
'''

dp_description

Value:
'''
Degree reverse lexicographic (degrevlex) term ordering.

Let $deg(x^a) = a_0 + ... + a_{n-1},$ then $x^a < x^b <=> deg(x^a) < d\
eg(x^b)$ or
$deg(x^a) = deg(x^b)$ and $\\exists\\ 0 <= i < n: a_{n-1} = b_{n-1}, .\
.., a_{i+1} = b_{i+1}, a_i > b_i.$
'''

Dp_description

Value:
'''
Degree lexicographic (deglex) term ordering.

Let $deg(x^a) = a_0 + \\cdots + a_{n-1},$ then $x^a < x^b \\Leftrighta\
rrow deg(x^a) < deg(x^b)$ or
$deg(x^a) = deg(x^b)$ and $\\exists\\ 0 \\le i < n:a_0 = b_0, \\ldots,\
 a_{i-1} = b_{i-1}, a_i < b_i.$
'''

rp_description

Value:
'''
Inverse lexicographic (invlex) term ordering.

$x^a < x^b \\Leftrightarrow \\exists\\; 0 \\le i < n : a_{n-1} = b_{n-\
1}, \\ldots, a_{i+1} = b_{i+1}, a_i < b_i.$
'''

ls_description

Value:
'''
Negative lexicographic (neglex) term ordering.

$x^a < x^b \\Leftrightarrow \\exists\\; 0 \\le i < n : a_0 = b_0, \\ld\
ots, a_{i-1} = b_{i-1}, a_i > b_i$
'''

ds_description

Value:
'''
Negative degree reverse lexicographic (negdegrevlex) term ordering.

Let $deg(x^a) = a_0 + \\cdots + a_{n-1},$ then $x^a < x^b \\Leftrighta\
rrow deg(x^a) > deg(x^b)$ or
$deg(x^a) = deg(x^b)$ and $\\exists\\ 0 \\le i < n: a_{n-1} = b_{n-1},\
 \\ldots, a_{i+1} = b_{i+1}, a_i > b_i.$
'''

Ds_description

Value:
'''
Negative degree lexicographic (negdeglex) term ordering.

Let $deg(x^a) = a_0 + \\cdots + a_{n-1},$ then $x^a < x^b \\Leftrighta\
rrow deg(x^a) > deg(x^b)$ or
$deg(x^a) = deg(x^b)$ and $\\exists\\ 0 \\le i < n: a_0 = b_0, \\ldots\
, a_{i-1} = b_{i-1}, a_i < b_i.$
'''

description_mapping

Value:
{'Dp': '''
Degree lexicographic (deglex) term ordering.

Let $deg(x^a) = a_0 + \\cdots + a_{n-1},$ then $x^a < x^b \\Leftrighta\
rrow deg(x^a) < deg(x^b)$ or
$deg(x^a) = deg(x^b)$ and $\\exists\\ 0 \\le i < n:a_0 = b_0, \\ldots,\
 a_{i-1} = b_{i-1}, a_i < b_i.$
''',
...

   Home       Trees       Indices       Help   
Generated by Epydoc 3.0beta1 on Thu Jul 17 04:23:28 2008 http://epydoc.sourceforge.net