Package sagbi

From ApCoCoAWiki

This page is about the SAGBI package. For a complete function list, see Category:Package sagbi.

Mathematical Definitions

Let be a field and let be the polynomial ring over in indeterminates. Most of the definitions here are taken from the book Computational Commutative Algebra 2 by Martin Kreuzer and Lorenzo Robbiano.


A subset is called a -subalgebra of , if

  • and
  • is closed under addition and multiplication.

For a subset , we write

where is a new polynomial ring in indeterminates for the -subalgebra of generated by .

SAGBI bases

Let be a term ordering on and let be a -subalgebra of . A set is called a -SAGBI basis of if .

If is a graded subalgebra and , then a set is called a -truncated -SAGBI basis of , if

Equivalently, a set is a -truncated -SAGBI basis of if there is a -SAGBI basis of with .

The Subalgebra Rewrite Relation

Let be a set of non-zero polynomials. Furthermore, let be a term ordering on .

  • For , we say that subalgebra reduces to in one step if there are , a term , and a constant such that and is not anymore in . The path from to is then called a subalgebra reduction step and denoted by .
  • The transitive closure of the relation is denoted by and called the subalgebra rewrite relation defined by . If there are with , we say that subalgebra reduces to .
  • If such that there is no with and , then is called irreducible with respect to the relation . Sometimes we may also just write that is irreducible with respect to .

A set is called interreduced if every element is monic and irreducible with respect to . If is a -SAGBI basis of which is interreduced, then it is called a reduced -SAGBI basis. Analogously to reduced Gröbner bases, it can be shown that every -subalgebra has a unique reduced -SAGBI basis.

The Subalgebra Division Algorithm

Let be a term ordering on , and be a set of non-zero polynomials. Consider the following sequence of instructions.

  1. Set .
  2. Write with , for , and . Set .
  3. If , stop and return . Otherwise, check whether there is a term such that . If there is one, set , replace by and go to step~(2). If there is none, increase by one and repeat this step.

This is an algorithm which returns a polynomial such that and is irreducible with respect to . This algorithm clearly computes a polynomial with and is irreducible with respect to .

Package Description

All of the previously described definitions are implemented in the SAGBI package.

Basic functions

Given a polynomial ring P and a list F of polynomials in P, one can compute the reduced SAGBI basis of [F] (with respect to the term ordering given by P) using the function SB.SAGBI - as long as a finite one exists.


Note that this function probably runs into an infinite loop if no finite SAGBI basis exists. This can be avoided using the function SB.SAGBITimeout. Given a positive integer s, one can type in


which does the same as SB.SAGBI(F), but throws an error if the computation is not finished within s seconds. Given a polynomial f and a list of polynomials G, the function SB.ReductionStep can be used to compute a polynomial g with fg.


If no such polynomial exists, then f is returned. This function is then used by the function SB.SDA, which is an implementation of the Subalgebra Division Algorithm described above.


Analogously to the CoCoA-5 function interreduced, the SAGBI package contains the function SB.Interreduced which takes as input a list of polynomials G and returns a list G' with .


Special Functions for Graded Subalgebras

If G is a set of homogeneous polynomials, then there are additional functions one can use. Given a positive integerd, a d-truncated SAGBI basis can be computed using SB.TruncSAGBI.


The function SB.SubalgebraHS can be applied to compute the Hilbert series of a graded subalgebra.


If furthermore G is a set of terms, then the function


can be used to compute its Hilbert series much more efficient.

The Subalgebra Data Type

The package also introduces a new Data type, i.e. a record tagged with "$apcocoa/sagbi.Subalgebra". Given a polynomial ring P and a list of polynomials G from P, one can create the subalgebra using the function SB.Subalgebra.

Use P ::= QQ[x,y,z];
G := [x^2+y*z,z];
S := SB.Subalgebra(P,G);

For details about the structure of this data type, see the function page. While nearly all functionalities of the SAGBI package can be used without touching this data type, it has many advantages to do so because it stores informations of previous computations, see the example below. This is also the reason why many of the getter functions need the subalgebra to be called by reference. The following getter function can be used to get informations about the subalgebra:

SB.GetCoeffRing(S); -- returns the coefficient ring
SB.GetGens(S); -- returns the set G
SB.GetID(S); -- returns the unique ID of S
SB.GetLTSA(ref S); -- returns the subalgebra K[LT(f) | f in S]
SB.GetRing(S); -- returns P
SB.GetSAGBI(ref S); -- returns the reduced SAGBI basis of S (if a finite one exists)

If additionally, G is a set of homogeneous polynomials, one can call the following getter functions:

SB.GetHS(ref S); -- returns the Hilbert Series of S
SB.GetTruncSAGBI(ref S,d); -- returns a d-truncated SAGBI basis of S
SB.GetTruncDeg(S); -- returns the truncation degree of the currently stored SAGBI basis

To optain a -vector space basis of the set of all homogeneous polynomials of degree in , the function SB.GetInDeg can be used:


Testing Subalgebra Membership

Let f be a polynomial in the polynomial ring P, let G be a list of polynomials in P and let S be a subalgebra generated by G. Then the SAGBI package provides four functions to check whether f is an element of the subalgebra S:


If G is a list of homogeneous polynomials, the following functions can also be used:

SB.IsInSA_SAGBI(f,ref S);

While the first two functions test the membership using implicitization, these two functions use truncated SAGBI bases for the membership test, which may be more efficient. It depends on the application which of these two possibilities is the fastest one.

Example for the Subalgebra Data Type

So what advantages does the Subalgebra data type have? Consider the following example.

Use P ::= QQ[x,y,z];
G := [x^2 -z^2,  x*y +z^2,  y^2 -2*z^2];
f := x^10*y^2 +x^6*y^6 -2*x^10*z^2 -5*x^8*y^2*z^2 +6*x^5*y^5*z^2 +10*x^8*z^4 +10*x^6*y^2*z^4 +15*x^4*y^4*z^4 -20*x^6*z^6 -10*x^4*y^2*z^6 +20*x^3*y^3*z^6 +20*x^4*z^8 +20*x^2*y^2*z^8 -10*x^2*z^10 +6*x*y*z^10 -y^2*z^10 +3*z^12;
b := SB.IsInSubalgebra(f,G);
h := SB.SubalgebraHS(G);

Here, first a SAGBI basis is computed, then the subalgebra membership is tested using implicitization and at the end, the Hilbert series of <math>K[G] is computed. But after computing a SAGBI basis, one could also test the Subalgebra membership using the Subalgebra Division Algorithm and compute the Hilbert Series of . The Subalgebra data type does this automatically. Instead of the code above, we can write the following:

Use P ::= QQ[x,y,z];
G := [x^2 -z^2,  x*y +z^2,  y^2 -2*z^2];
S := SB.Subalgebra(P,G);
L := SB.GetSAGBI(S);
f := x^10*y^2 +x^6*y^6 -2*x^10*z^2 -5*x^8*y^2*z^2 +6*x^5*y^5*z^2 +10*x^8*z^4 +10*x^6*y^2*z^4 +15*x^4*y^4*z^4 -20*x^6*z^6 -10*x^4*y^2*z^6 +20*x^3*y^3*z^6 +20*x^4*z^8 +20*x^2*y^2*z^8 -10*x^2*z^10 +6*x*y*z^10 -y^2*z^10 +3*z^12;
b := SB.IsInSA(f,S);
h := SB.GetHS(S);

While this is only a simple example, the second code is much faster. At the time this is written, the second computation is approximately two times as fast as the first one.