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.
Let K be a field, let be the polynomial ring over K in n indeterminates and let be the set of all power products in P.
Let be a total order on T(P). For a pair , we write . Then is called a term ordering on T(P) iff it is multiplicative, i.e. implies for each , and we have for all terms .
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 of f and
- 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 P in the following way: For two vectors we define if either v = w or the first non-zero entry of w-v is positive. Then Ord(M) is defined by
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 Ord(M). Using the call
OrdMat(P), we can then check that
P is indeed ordered by the matrix
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 s rows where , one can call
MakeTermOrd(M) to get a term ordering matrix whose first s rows are the original matrix
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 P corresponding to the indices in L are 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.
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 - x^2; /**/ f2 := y - x^2; /**/ f3 := y - x*x; /**/ I := ideal(f1,f2,f3);
Furthermore, suppose that we want to compute the intersection of I with the ring R = QQ[y,y,y]. 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*y -y^2. This shows that .