Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ExtendedGroebnerBasis

Source Notebook

Compute a Groebner basis and a conversion matrix from the input polynomials to the basis

Contributed by: Daniel Lichtblau

ResourceFunction["ExtendedGroebnerBasis"][polys,vars]

gives the Groebner basis 𝒢 for the polynomial list polys along with a polynomial conversion matrix ℳ satisfying 𝒢=ℳ·polys.

Details and Options

ResourceFunction["ExtendedGroebnerBasis"] takes the same optional arguments and options as GroebnerBasis.

Examples

Basic Examples (5) 

Create a set of polynomials:

In[1]:=
polys = {x^2 + 3*y - 2*z^4 + 7, 5*x^2*y*z - 4*y^2*z^2 + 3, x^2 + y^2 + z^3 - 6};

First compute its Groebner basis:

In[2]:=
gb1 = GroebnerBasis[polys, {x, y, z}]
Out[2]=

Compute the extended Groebner basis:

In[3]:=
{gb2, cmat} = ResourceFunction["ExtendedGroebnerBasis"][polys, {x, y, z}]
Out[3]=

Check that the bases agree up to a constant factor:

In[4]:=
Together[gb1/gb2]
Out[4]=

Check the conversion matrix identity:

In[5]:=
Expand[cmat . polys - gb2]
Out[5]=

Scope (3) 

Here is a larger example:

In[6]:=
polys = {x^2 + 3*y - 2*z^4 + 7, -x^3*z + 5*x^2*y^2*z - 4*y^2*z^3 + 3, x^3 + y^3 + 2*z^3 - 6}; gb1 = GroebnerBasis[polys, {x, y, z}, MonomialOrder -> DegreeReverseLexicographic]
Out[7]=
In[8]:=
{gb2, cmat} = ResourceFunction["ExtendedGroebnerBasis"][polys, {x, y, z}, MonomialOrder -> DegreeReverseLexicographic]
Out[8]=

Check that the bases agree up to constant factors (they are not identical in this instance):

In[9]:=
Together[gb1/gb2]
Out[9]=

Check the conversion matrix identity:

In[10]:=
Expand[cmat . polys - gb2]
Out[10]=

Properties and Relations (7) 

The Groebner basis of a pair of univariate polynomials is their greatest common divisor, and similarly the extended Groebner basis gives the extended GCD. Create a pair of polynomials with a known common divisor poly1:

In[11]:=
randomPoly[deg_, x_, cmax_] := x^deg + RandomInteger[{-cmax, cmax}, deg] . x^Range[0, deg - 1] SeedRandom[1234] poly1 = randomPoly[4, x, 9]; poly2 = randomPoly[4, x, 9]; poly3 = randomPoly[4, x, 9]; poly12 = Expand[poly1*poly2]; poly13 = Expand[poly1*poly3]; polys = {poly12, poly13};

Compute the extended GCD:

In[12]:=
{gcd, mat} = ResourceFunction["ExtendedGroebnerBasis"][polys]
Out[12]=

Check that the single polynomial in the Groebner basis is a GCD (a constant multiple of poly1):

In[13]:=
Together[gcd[[1]]/poly1]
Out[13]=

Check the Bezout relation for the extended GCD:

In[14]:=
Expand[mat . polys - gcd]
Out[14]=

Compare to PolynomialExtendedGCD:

In[15]:=
{gcd2, vec} = PolynomialExtendedGCD[poly12, poly13, x]
Out[15]=

Again check the Bezout relation:

In[16]:=
Expand[vec . polys - gcd2]
Out[16]=

Now check that these two computations agree up to a constant factor:

In[17]:=
Together[{gcd, mat[[1]]}/{gcd2, vec}]
Out[17]=

Possible Issues (1) 

ExtendedGroebnerBasis can be much slower that GroebnerBasis for the same input:

In[18]:=
polys = {x^3 + 3*x^2 y^3 z - 2*z^4 + 7, -x^3*z + 5*x^2*y^2*z^2 - 4*y^2*z^3 + 3, x^4 z + y^4 + 2*z^4 - 6}; Timing[GroebnerBasis[polys, {x, y, z}];]
Out[18]=
In[19]:=
Timing[ResourceFunction["ExtendedGroebnerBasis"][polys, {x, y, z}];]
Out[19]=

Version History

  • 1.0.0 – 27 September 2019

Related Resources

License Information