# Difference between revisions of "HowTo:Term Orderings"

Andraschko (talk | contribs) (Small start (not finished yet)) |
Andraschko (talk | contribs) (finished HoTo) |
||

Line 4: | Line 4: | ||

Let ''K'' be a field, let <math>P = K[x_1,\ldots,x_n]</math> be the polynomial ring over '''''K''''' in '''''n''''' indeterminates and let <math>\mathbb{T}(P) = \{x_1^{\alpha_1}\cdots x_n^{\alpha_n} \mid \alpha_1,\ldots,\alpha_n \in \mathbb{N}_0\}</math> be the set of all power products in '''''P'''''. | Let ''K'' be a field, let <math>P = K[x_1,\ldots,x_n]</math> be the polynomial ring over '''''K''''' in '''''n''''' indeterminates and let <math>\mathbb{T}(P) = \{x_1^{\alpha_1}\cdots x_n^{\alpha_n} \mid \alpha_1,\ldots,\alpha_n \in \mathbb{N}_0\}</math> be the set of all power products in '''''P'''''. | ||

− | Let <math>\sigma</math> be a total order on '''''T(P)'''''. For a pair <math>(t_1,t_2) \in \sigma</math>, we write <math>t_1 \leq_\sigma t_2</math. Then <math>\sigma</math> is called a '''term ordering''' on '''''T(P)''''' iff it is multiplicative, i.e. <math>t_1 \leq_\sigma t_2</math> implies <math>st_1\leq_\sigma st_2</math> for each <math>t_1,t_2,s \in \mathbb{T}(P)</math>, and we have <math>1 \leq_\sigma t</math> for all terms <math>t \in \mathbb{T}(P)</math>. | + | Let <math>\sigma</math> be a total order on '''''T(P)'''''. For a pair <math>(t_1,t_2) \in \sigma</math>, we write <math>t_1 \leq_\sigma t_2</math>. Then <math>\sigma</math> is called a '''term ordering''' on '''''T(P)''''' iff it is multiplicative, i.e. <math>t_1 \leq_\sigma t_2</math> implies <math>st_1\leq_\sigma st_2</math> for each <math>t_1,t_2,s \in \mathbb{T}(P)</math>, and we have <math>1 \leq_\sigma t</math> for all terms <math>t \in \mathbb{T}(P)</math>. |

For a polynomial <math>f \in P</math>, we can write <math>f = c_1t_1 + \cdots + c_st_s</math> where <math>t_i \in \mathbb{T}(P)</math> and <math>c_i \in K^\times</math> for each '''''i''''' such that <math>t_1 >_\sigma \cdots >_\sigma t_s</math>. Then we use the following notation | For a polynomial <math>f \in P</math>, we can write <math>f = c_1t_1 + \cdots + c_st_s</math> where <math>t_i \in \mathbb{T}(P)</math> and <math>c_i \in K^\times</math> for each '''''i''''' such that <math>t_1 >_\sigma \cdots >_\sigma t_s</math>. Then we use the following notation | ||

Line 10: | Line 10: | ||

*<math>{\rm LC}_\sigma(f) = c_1</math> is the '''leading monomial''' of '''''f''''' and | *<math>{\rm LC}_\sigma(f) = c_1</math> is the '''leading monomial''' of '''''f''''' and | ||

*<math>{\rm LM}_\sigma(f) = c_1t_1</math> is the '''leading coefficient''' of '''''f'''''. | *<math>{\rm LM}_\sigma(f) = c_1t_1</math> is the '''leading coefficient''' of '''''f'''''. | ||

+ | |||

+ | Given a matrix <math>M = (a_{ij}) \in {\rm GL}_n(\mathbb{Q})</math> such that the first entry of every column is positive, we can define a term ordering ordering '''''Ord(M)''''' on '''''P''''' in the following way: For two vectors <math>v, w \in K^n</math> we define <math>v \leq_{\texttt{Lex}} w</math> if either '''''v = w''''' or the first non-zero entry of '''''w-v''''' is positive. Then '''''Ord(M)''''' is defined by | ||

+ | :<math>x_1^{\alpha_1}\cdots x_n^{\alpha_n} \leq_{{\rm Ord}(M)} x_1^{\beta_1}\cdots x_n^{\beta_n} \iff M \cdot (\alpha_1,\ldots,\alpha_n)^{\rm tr} \leq_{\texttt{Lex}} M \cdot (\beta_1,\ldots,\beta_n)^{\rm tr}</math>. | ||

+ | It is easy to show that this defines a term ordering on '''''P'''''. | ||

+ | |||

+ | == Term Orderings in CoCoA == | ||

+ | In CoCoA, term orderings are defined in the definition of polynomial rings and can not be changed later during the computation. | ||

+ | === Setting up a Term Ordering === | ||

+ | At top-level, the currently available term orderings are | ||

+ | Use P ::= QQ[x,y,z], Lex; | ||

+ | Use P ::= QQ[x,y,z], DegLex; | ||

+ | Use P ::= QQ[x,y,z], DegRevLex; | ||

+ | These calls create the ring <math>P := \mathbb{Q}[x,y,z]</math> with the corresponding term orderings. These term orderings correspond to the matrices | ||

+ | :<math>M_{\texttt{Lex}} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}</math> | ||

+ | :<math>M_{\texttt{DegLex}} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}</math> | ||

+ | :<math>M_{\texttt{DegRevLex}} = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 0 & -1 \\ 0 & -1 & 0 \end{pmatrix}</math> | ||

+ | The default term odering is <tt>DegRevLex</tt> if no order is specified. | ||

+ | |||

+ | For term orderings different for the ones above, one can use the function <code>NewPolyRing</code> to create an ordered polynomial ring. Given a base ring <code>R</code> (which does not have to be a field), a String or a list <code>L</code> of indeterminates (for details, see the description of the function in CoCoA) and a matrix <code>M</code> corresponding to a term ordering, one can call | ||

+ | P := NewPolyRing(R, "x,y,z", M, 1); | ||

+ | in order to create the polynomial ring '''''R[x,y,z]''''' which is ordered by '''''Ord(M)'''''. Using the call <code>OrdMat(P)</code>, we can then check that <code>P</code> is indeed ordered by the matrix <code>M</code>. | ||

+ | |||

+ | There are also a couple of functions that help creating a term ordering. For instance, if we already have matrix <code>M</code> with '''''n''''' columns, only '''''s''''' rows where <math>s < n</math>, one can call <code>MakeTermOrd(M)</code> to get a term ordering matrix whose first '''''s''''' rows are the original matrix <code>M</code>. For some fixed term orderings, one can use the functions <code>LexMat(n), XelMat(n), StdDegLexMat(n), StdDegRevLexMat(n)</code>. | ||

+ | <pre> | ||

+ | /**/ MakeTermOrd(matrix([[1,2,3]])); | ||

+ | matrix(ZZ, | ||

+ | [[1, 2, 3], | ||

+ | [0, 0,-1], | ||

+ | [0,-1, 0]]) | ||

+ | /**/ LexMat(3); | ||

+ | matrix(ZZ, | ||

+ | [[1, 0, 0], | ||

+ | [0, 1, 0], | ||

+ | [0, 0, 1]]) | ||

+ | /**/ XelMat(3); | ||

+ | matrix(ZZ, | ||

+ | [[0, 0, 1], | ||

+ | [0, 1, 0], | ||

+ | [1, 0, 0]]) | ||

+ | /**/ StdDegLexMat(3); | ||

+ | matrix(ZZ, | ||

+ | [[1, 1, 1], | ||

+ | [1, 0, 0], | ||

+ | [0, 1, 0]]) | ||

+ | /**/ StdDegRevLexMat(3); | ||

+ | matrix(ZZ, | ||

+ | [[1, 1, 1], | ||

+ | [0, 0,-1], | ||

+ | [0,-1, 0]]) | ||

+ | </pre> | ||

+ | A special command is the function <code>ElimMat</code>. Given a polynomial ring <math>P = K[x_1,\ldots,x_n]</math> and a list <code>L</code> which is a the call <code>ElimMat(L,n)</code> produces a matrix '''''M''''' corresponding to an elimination ordering for <math>\{x_i \mid i \in L\}</math>, i.e. an odering <math>\sigma</math> such that <math>{\rm LT}_\sigma(f) \in K[x_l \mid l \not\in L] \iff f \in K[x_l \mid l \not\in L]</math>, or - more informally - the indeterminates of '''''P''''' corresponding to the indices in '''''L''''' are ''infinitely larger'' than the other ones. | ||

+ | <pre> | ||

+ | /**/ ElimMat([1,2],4); | ||

+ | matrix(ZZ, | ||

+ | [[1, 1, 0, 0], | ||

+ | [1, 1, 1, 1], | ||

+ | [0, 0, 0,-1], | ||

+ | [0,-1, 0, 0]]) | ||

+ | </pre> | ||

+ | |||

+ | === Working with an Ordered Polynomial Ring === | ||

+ | In CoCoA, polynomials are elements of rings and rings already fix a term ordering. This means, that the leading term of a polynomial in CoCoA does only depend on the ring which the polynomial is an element of. Therefore, the calls <code>LT(f), LC(f), LM(f)</code> are well-defined and do not need the ordering as an additional argument like the mathematical description <math>{\rm LT_\sigma(f)</math>. | ||

+ | |||

+ | Also the function <code>GBasis(I)</code> for computing a Gröbner basis of an ideal <code>I</code> does not need the term ordering as an argument as it is already fixed in the definition of the ring <code>RingOf(I)</code>. For the same reason, the call <code>LT(I)</code> is well-defined. | ||

+ | |||

+ | === Switching Orderings === | ||

+ | While there is no way to change the term ordering of a ring, there is the possibility of creating a new polynomial ring an mapping the elements between them. For instance, suppose we have an ideal '''I''' in a ring '''P''', but want to compute a Gröbner basis of '''I''' with respect to a different term ordering given by a matrix '''M'''. Then one can use the following: | ||

+ | <pre> | ||

+ | /**/ Q := NewPolyRing(CoeffRing(P), SymbolRange("x",1,NumIndets(P)), M, 1); | ||

+ | /**/ phi := PolyAlgebraHom(P, Q, indets(Q)); | ||

+ | /**/ I_Q := ideal(apply(phi, gens(I))); | ||

+ | /**/ GB_Q := GBasis(I_Q); -- a list of polynomials in Q | ||

+ | /**/ GB_P := [ preimage0(phi, g) | g in GB_Q ]; | ||

+ | </pre> | ||

+ | '''Note''': If you now print out the result with <code>GB_P</code>, then the polynomials are printed out as elements of '''P''', so their leading terms now most likely do not generate the leading term ideal of '''I'''. | ||

+ | |||

+ | === A Small Example === | ||

+ | Suppose, we start with the following code: | ||

+ | <pre> | ||

+ | /**/ Use P ::= QQ[y[1..3],x[1..2]]; -- std ordering is DegRevLex | ||

+ | /**/ f1 := y[1] - x[1]^2; | ||

+ | /**/ f2 := y[2] - x[2]^2; | ||

+ | /**/ f3 := y[3] - x[1]*x[2]; | ||

+ | /**/ I := ideal(f1,f2,f3); | ||

+ | </pre> | ||

+ | Furthermore, suppose that we want to compute the intersection of '''I''' with the ring '''''R = QQ[y[1],y[2],y[3]]'''''. Then we apply the code described above: | ||

+ | <pre> | ||

+ | /**/ M := ElimMat([4,5], 5); | ||

+ | /**/ Q := NewPolyRing(CoeffRing(P), SymbolRange("x",1,NumIndets(P)), M, 1); | ||

+ | /**/ phi := PolyAlgebraHom(P, Q, indets(Q)); | ||

+ | /**/ I_Q := ideal(apply(phi, gens(I))); | ||

+ | /**/ GB_Q := GBasis(I_Q); | ||

+ | /**/ GB_P := [ preimage0(phi, g) | g in GB_Q ]; | ||

+ | </pre> | ||

+ | If we now print out <code>GB_P</code>, we see that the only polynomial in its intersection with '''''R''''' is <code>y[1]*y[2] -y[3]^2</code>. This shows that <math>I \cap R = \langle y_{1} y_{2} -y_{3}^2 \rangle_R</math>. | ||

+ | |||

+ | |||

+ | [[Category:HowTo]] |

## Revision as of 11:25, 14 February 2021

This page is an introduction into term orderings in CoCoA-5 or ApCoCoA-2. In order to understand this topic, we assume that the reader is familiar with the concept of term orderings on polynomial rings.

## Mathematical definition

Let *K* be a field, let be the polynomial ring over * K* in

*indeterminates and let be the set of all power products in*

**n***.*

**P**Let be a total order on * T(P)*. For a pair , we write . Then is called a

**term ordering**on

*iff it is multiplicative, i.e. implies for each , and we have for all terms .*

**T(P)**For a polynomial , we can write where and for each * i* such that . Then we use the following notation

- is the
**leading terms**of,**f** - is the
**leading monomial**ofand**f** - is the
**leading coefficient**of.**f**

Given a matrix such that the first entry of every column is positive, we can define a term ordering ordering * Ord(M)* on

*in the following way: For two vectors we define if either*

**P***or the first non-zero entry of*

**v = w***is positive. Then*

**w-v***is defined by*

**Ord(M)**- .

It is easy to show that this defines a term ordering on * P*.

## Term Orderings in CoCoA

In CoCoA, term orderings are defined in the definition of polynomial rings and can not be changed later during the computation.

### Setting up a Term Ordering

At top-level, the currently available term orderings are

Use P ::= QQ[x,y,z], Lex; Use P ::= QQ[x,y,z], DegLex; Use P ::= QQ[x,y,z], DegRevLex;

These calls create the ring with the corresponding term orderings. These term orderings correspond to the matrices

The default term odering is `DegRevLex` if no order is specified.

For term orderings different for the ones above, one can use the function `NewPolyRing`

to create an ordered polynomial ring. Given a base ring `R`

(which does not have to be a field), a String or a list `L`

of indeterminates (for details, see the description of the function in CoCoA) and a matrix `M`

corresponding to a term ordering, one can call

P := NewPolyRing(R, "x,y,z", M, 1);

in order to create the polynomial ring * R[x,y,z]* which is ordered by

*. Using the call*

**Ord(M)**`OrdMat(P)`

, we can then check that `P`

is indeed ordered by the matrix `M`

.
There are also a couple of functions that help creating a term ordering. For instance, if we already have matrix `M`

with * n* columns, only

*rows where , one can call*

**s**`MakeTermOrd(M)`

to get a term ordering matrix whose first *rows are the original matrix*

**s**`M`

. For some fixed term orderings, one can use the functions `LexMat(n), XelMat(n), StdDegLexMat(n), StdDegRevLexMat(n)`

.
/**/ MakeTermOrd(matrix([[1,2,3]])); matrix(ZZ, [[1, 2, 3], [0, 0,-1], [0,-1, 0]]) /**/ LexMat(3); matrix(ZZ, [[1, 0, 0], [0, 1, 0], [0, 0, 1]]) /**/ XelMat(3); matrix(ZZ, [[0, 0, 1], [0, 1, 0], [1, 0, 0]]) /**/ StdDegLexMat(3); matrix(ZZ, [[1, 1, 1], [1, 0, 0], [0, 1, 0]]) /**/ StdDegRevLexMat(3); matrix(ZZ, [[1, 1, 1], [0, 0,-1], [0,-1, 0]])

A special command is the function `ElimMat`

. Given a polynomial ring and a list `L`

which is a the call `ElimMat(L,n)`

produces a matrix * M* corresponding to an elimination ordering for , i.e. an odering such that , or - more informally - the indeterminates of

*corresponding to the indices in*

**P***are*

**L***infinitely larger*than the other ones.

/**/ ElimMat([1,2],4); matrix(ZZ, [[1, 1, 0, 0], [1, 1, 1, 1], [0, 0, 0,-1], [0,-1, 0, 0]])

### Working with an Ordered Polynomial Ring

In CoCoA, polynomials are elements of rings and rings already fix a term ordering. This means, that the leading term of a polynomial in CoCoA does only depend on the ring which the polynomial is an element of. Therefore, the calls `LT(f), LC(f), LM(f)`

are well-defined and do not need the ordering as an additional argument like the mathematical description **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\rm LT_\sigma(f)}**
.

Also the function `GBasis(I)`

for computing a Gröbner basis of an ideal `I`

does not need the term ordering as an argument as it is already fixed in the definition of the ring `RingOf(I)`

. For the same reason, the call `LT(I)`

is well-defined.

### Switching Orderings

While there is no way to change the term ordering of a ring, there is the possibility of creating a new polynomial ring an mapping the elements between them. For instance, suppose we have an ideal **I** in a ring **P**, but want to compute a Gröbner basis of **I** with respect to a different term ordering given by a matrix **M**. Then one can use the following:

/**/ Q := NewPolyRing(CoeffRing(P), SymbolRange("x",1,NumIndets(P)), M, 1); /**/ phi := PolyAlgebraHom(P, Q, indets(Q)); /**/ I_Q := ideal(apply(phi, gens(I))); /**/ GB_Q := GBasis(I_Q); -- a list of polynomials in Q /**/ GB_P := [ preimage0(phi, g) | g in GB_Q ];

**Note**: If you now print out the result with `GB_P`

, then the polynomials are printed out as elements of **P**, so their leading terms now most likely do not generate the leading term ideal of **I**.

### A Small Example

Suppose, we start with the following code:

/**/ Use P ::= QQ[y[1..3],x[1..2]]; -- std ordering is DegRevLex /**/ f1 := y[1] - x[1]^2; /**/ f2 := y[2] - x[2]^2; /**/ f3 := y[3] - x[1]*x[2]; /**/ I := ideal(f1,f2,f3);

Furthermore, suppose that we want to compute the intersection of **I** with the ring * R = QQ[y[1],y[2],y[3]]*. Then we apply the code described above:

/**/ M := ElimMat([4,5], 5); /**/ Q := NewPolyRing(CoeffRing(P), SymbolRange("x",1,NumIndets(P)), M, 1); /**/ phi := PolyAlgebraHom(P, Q, indets(Q)); /**/ I_Q := ideal(apply(phi, gens(I))); /**/ GB_Q := GBasis(I_Q); /**/ GB_P := [ preimage0(phi, g) | g in GB_Q ];

If we now print out `GB_P`

, we see that the only polynomial in its intersection with * R* is

`y[1]*y[2] -y[3]^2`

. This shows that .