# Difference between revisions of "HowTo:Term Orderings"

Andraschko (talk | contribs) (finished HoTo) |
Andraschko (talk | contribs) m (fixed latex error) |
||

Line 71: | Line 71: | ||

=== Working with an Ordered Polynomial Ring === | === 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 | + | 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. | 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. |

## Latest revision as of 11:26, 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 .

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 .