Package sagbi

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

Mathematical Definitions

Let $K$ be a field and let $P=K[x_{1},\ldots ,x_{n}]$ be the polynomial ring over $K$ in $n$ indeterminates. Most of the definitions here are taken from the book Computational Commutative Algebra 2 by Martin Kreuzer and Lorenzo Robbiano.

Subalgebras

A subset $S\subseteq P$ is called a $K$-subalgebra of $P$, if

• $K\subseteq S$ and
• $S$ is closed under addition and multiplication.

For a subset $F=\{f_{1},\ldots ,f_{s}\}\subseteq P$, we write

$K[F]=K[f_{1},\ldots ,f_{s}]=\{p(f_{1},\ldots ,f_{s})\mid p\in K[y_{1},\ldots ,y_{s}]\}$

where $K[y_{1},\ldots ,y_{s}]$ is a new polynomial ring in $s$ indeterminates for the $K$-subalgebra of $P$ generated by $F$.

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 $K$[F] (with respect to the term ordering given by P) using the function SB.SAGBI - as long as a finite one exists.

SB.SAGBI(F);

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

SB.SAGBITimeout(F,s);

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 f${\xrightarrow {G} }_{\rm {s}}$g.

SB.ReductionStep(f,G);

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.

SB.SDA(f,G)

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 $K[G]=K[G']$.

SB.Interreduced(G);

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.

SB.TruncSAGBI(G,d);

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

SB.SubalgebraHS(G);

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

SB.TorRingHS(G);

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 $K[G]$ 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 $K$-vector space basis of the set $K[G]_{d}$ of all homogeneous polynomials of degree $d$ in $K[G]$, the function SB.GetInDeg can be used:

SB.GetInDeg(S);

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:

SB.IsInSubalgebra(f,G);
SB.IsInSA(f,S);

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

SB.IsInSubalgebra_SAGBI(f,G);
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];
L := SB.SAGBI(G);
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.