# Difference between revisions of "Package sagbi"

Line 20: | Line 20: | ||

=== The Subalgebra Rewrite Relation === | === The Subalgebra Rewrite Relation === | ||

− | |||

Let <math>G \subseteq P</math> be a set of non-zero polynomials. Furthermore, let <math>\sigma</math> be a term ordering on <math>\mathbb{T}^n</math>. | Let <math>G \subseteq P</math> be a set of non-zero polynomials. Furthermore, let <math>\sigma</math> be a term ordering on <math>\mathbb{T}^n</math>. | ||

* For <math>f, g \in P \setminus \{0\}</math>, we say that <math>f</math> '''subalgebra reduces to <math>g</math> in one step''' if there are <math>f_1,\ldots,f_s \in G</math>, a term <math>t \in \mathbb{T}^s</math>, and a constant <math>c \in K</math> such that <math>g = f - c t(f_1,\ldots,f_s)</math> and <math>{\rm LT}_\sigma(t(f_1,\ldots,f_s))</math> is not anymore in <math>{\operatorname{Supp}}(g)</math>. The path from <math>f</math> to <math>g</math> is then called a '''subalgebra reduction step''' and denoted by <math>f {\xrightarrow{G}}_{\rm ss} g</math>. | * For <math>f, g \in P \setminus \{0\}</math>, we say that <math>f</math> '''subalgebra reduces to <math>g</math> in one step''' if there are <math>f_1,\ldots,f_s \in G</math>, a term <math>t \in \mathbb{T}^s</math>, and a constant <math>c \in K</math> such that <math>g = f - c t(f_1,\ldots,f_s)</math> and <math>{\rm LT}_\sigma(t(f_1,\ldots,f_s))</math> is not anymore in <math>{\operatorname{Supp}}(g)</math>. The path from <math>f</math> to <math>g</math> is then called a '''subalgebra reduction step''' and denoted by <math>f {\xrightarrow{G}}_{\rm ss} g</math>. | ||

Line 26: | Line 25: | ||

* If <math>g \in P</math> such that there is no <math>h \in P</math> with <math>h \neq g</math> and <math>g {\xrightarrow{G}}_{\rm ss} h</math>, then <math>g</math> is called '''irreducible''' with respect to the relation <math>{\xrightarrow{G}}_{\rm s}</math>. Sometimes we may also just write that <math>g</math> is irreducible with respect to <math>G</math>. | * If <math>g \in P</math> such that there is no <math>h \in P</math> with <math>h \neq g</math> and <math>g {\xrightarrow{G}}_{\rm ss} h</math>, then <math>g</math> is called '''irreducible''' with respect to the relation <math>{\xrightarrow{G}}_{\rm s}</math>. Sometimes we may also just write that <math>g</math> is irreducible with respect to <math>G</math>. | ||

A set <math>G \subseteq P</math> is called '''interreduced''' if every element <math>g \in G</math> is monic and irreducible with respect to <math>G \setminus \{g\}</math>. If <math>G</math> is a <math>\sigma</math>-SAGBI basis of <math>K[G]</math> which is interreduced, then it is called a '''reduced <math>\sigma</math>-SAGBI basis'''. Analogously to reduced Gröbner bases, it can be shown that every <math>K</math>-subalgebra has a unique reduced <math>\sigma</math>-SAGBI basis. | A set <math>G \subseteq P</math> is called '''interreduced''' if every element <math>g \in G</math> is monic and irreducible with respect to <math>G \setminus \{g\}</math>. If <math>G</math> is a <math>\sigma</math>-SAGBI basis of <math>K[G]</math> which is interreduced, then it is called a '''reduced <math>\sigma</math>-SAGBI basis'''. Analogously to reduced Gröbner bases, it can be shown that every <math>K</math>-subalgebra has a unique reduced <math>\sigma</math>-SAGBI basis. | ||

− | |||

=== The Subalgebra Division Algorithm === | === The Subalgebra Division Algorithm === |

## Revision as of 09:24, 29 October 2020

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.

### Subalgebras

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

## 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.

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`

`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 .

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 integer`d`

, 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 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:

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.