In [1]:

    

from sympy import *
init_printing()
from sympy.polys import groebnertools as gt

import itertools as it


    

In [2]:

    

def S_poly(p, q):
    kgv = p.leading_monom().lcm(q.leading_monom())
    t1 = kgv / p.leading_term() * p
    t2 = kgv / q.leading_term() * q
    return t1 - t2

def log(verbose, msg):
    if verbose: print(msg)

def calc_groebner(G, verbose = False):
    G = G[:]
    while True:
        n = len(G)
        for f, g in it.combinations(G, 2):
            S = S_poly(f, g).div(G)[1]
            log(verbose, "Berechne S(" + str(f) + ", " + str(g) +") = " + str(S_poly(f, g)))
            log(verbose, "Rest davon bei Division durch G = " + str(S))
            if S != 0:
                G.append(S)
                log(verbose, "Erhalte neues G = " + str(G) + "\n")
                break
        if n == len(G): break
    log(verbose, "\nWir haben also eine GB gefunden: " + str(G))
    return G

def reduce_groebner(G):
    G = G[:]
    # Leitkoeffizienten normieren
    G = list(map(lambda p: p / p.LC, G))
    
    def is_div_LT(p, Gt):
        LT = lambda p: p.leading_monom()
        return any(LT(p).div(LT(f))[1] == 0 for f in Gt)
    
    def div_rem(p, Gt):
        return p.div(Gt)[1]
    
    # Polynome deren Leitterme durch Leitterme anderer
    # Polynome teilbar sind herausfiltern
    i = 0
    while i < len(G):
        if is_div_LT(G[i], G[:i] + G[i+1:]): del G[i]
        else: i += 1

    # Jedes Polynom mit seinem Rest beim Dividieren durch den
    # Rest der GB ersetzen. siehe Bew. von Thm 4.22
    for i in range(len(G)):
        G[i] = div_rem(G[i], G[:i] + G[i+1:])

    return G


    

In [3]:

    

P, (x, y, z) = xring('x,y,z', QQ, lex)
G = [x**2 - y, x**3 - z]


    

In [4]:

    

G = calc_groebner(G, verbose = True);


    

    




Berechne S(x**2 - y, x**3 - z) = -x*y + z
Rest davon bei Division durch G = -x*y + z
Erhalte neues G = [x**2 - y, x**3 - z, -x*y + z]

Berechne S(x**2 - y, x**3 - z) = -x*y + z
Rest davon bei Division durch G = 0
Berechne S(x**2 - y, -x*y + z) = x*z - y**2
Rest davon bei Division durch G = x*z - y**2
Erhalte neues G = [x**2 - y, x**3 - z, -x*y + z, x*z - y**2]

Berechne S(x**2 - y, x**3 - z) = -x*y + z
Rest davon bei Division durch G = 0
Berechne S(x**2 - y, -x*y + z) = x*z - y**2
Rest davon bei Division durch G = 0
Berechne S(x**2 - y, x*z - y**2) = x*y**2 - y*z
Rest davon bei Division durch G = 0
Berechne S(x**3 - z, -x*y + z) = x**2*z - y*z
Rest davon bei Division durch G = 0
Berechne S(x**3 - z, x*z - y**2) = x**2*y**2 - z**2
Rest davon bei Division durch G = y**3 - z**2
Erhalte neues G = [x**2 - y, x**3 - z, -x*y + z, x*z - y**2, y**3 - z**2]

Berechne S(x**2 - y, x**3 - z) = -x*y + z
Rest davon bei Division durch G = 0
Berechne S(x**2 - y, -x*y + z) = x*z - y**2
Rest davon bei Division durch G = 0
Berechne S(x**2 - y, x*z - y**2) = x*y**2 - y*z
Rest davon bei Division durch G = 0
Berechne S(x**2 - y, y**3 - z**2) = x**2*z**2 - y**4
Rest davon bei Division durch G = 0
Berechne S(x**3 - z, -x*y + z) = x**2*z - y*z
Rest davon bei Division durch G = 0
Berechne S(x**3 - z, x*z - y**2) = x**2*y**2 - z**2
Rest davon bei Division durch G = 0
Berechne S(x**3 - z, y**3 - z**2) = x**3*z**2 - y**3*z
Rest davon bei Division durch G = 0
Berechne S(-x*y + z, x*z - y**2) = y**3 - z**2
Rest davon bei Division durch G = 0
Berechne S(-x*y + z, y**3 - z**2) = x*z**2 - y**2*z
Rest davon bei Division durch G = 0
Berechne S(x*z - y**2, y**3 - z**2) = x*z**3 - y**5
Rest davon bei Division durch G = 0

Wir haben also eine GB gefunden: [x**2 - y, x**3 - z, -x*y + z, x*z - y**2, y**3 - z**2]

In [5]:

    

G = reduce_groebner(G); G


    

    
Out[5]:





[x**2 - y, x*y - z, x*z - y**2, y**3 - z**2]

In [6]:

    

# Sanity check.
gt.groebner(G, P)


    

    
Out[6]:





[x**2 - y, x*y - z, x*z - y**2, y**3 - z**2]

In [7]:

    

P, (x, y, z) = xring('x,y,z', QQ, grevlex)
G = [y - x**3, x**2*y - z]
f = x*y**3 - z**2 + y**5 - z**3

G = calc_groebner(G, verbose = True);


    

    




Berechne S(-x**3 + y, x**2*y - z) = -y**2 + x*z
Rest davon bei Division durch G = -y**2 + x*z
Erhalte neues G = [-x**3 + y, x**2*y - z, -y**2 + x*z]

Berechne S(-x**3 + y, x**2*y - z) = -y**2 + x*z
Rest davon bei Division durch G = 0
Berechne S(-x**3 + y, -y**2 + x*z) = x**4*z - y**3
Rest davon bei Division durch G = 0
Berechne S(x**2*y - z, -y**2 + x*z) = x**3*z - y*z
Rest davon bei Division durch G = 0

Wir haben also eine GB gefunden: [-x**3 + y, x**2*y - z, -y**2 + x*z]

In [8]:

    

# Dass der Rest beim Dividieren durch die GB 0 wird sagt uns,
# dass das Polynom f tatsächlich in dem Ideal liegt.
f.div(G)


    

    
Out[8]:





([0, z**2 + z, -y**3 - x*y*z - x*y], 0)

In [9]:

    

# Sanity check.
print(reduce_groebner(G))
gt.groebner(G, P)


    

    




[x**3 - y, x**2*y - z, y**2 - x*z]






    
Out[9]:





[x**3 - y, x**2*y - z, y**2 - x*z]

In [10]:

    

P, (x, y, z) = xring('x,y,z', QQ, lex)
G = [y - x**3, x**2*y - z]

G = calc_groebner(G, verbose = True);


    

    




Berechne S(-x**3 + y, x**2*y - z) = x*z - y**2
Rest davon bei Division durch G = x*z - y**2
Erhalte neues G = [-x**3 + y, x**2*y - z, x*z - y**2]

Berechne S(-x**3 + y, x**2*y - z) = x*z - y**2
Rest davon bei Division durch G = 0
Berechne S(-x**3 + y, x*z - y**2) = x**2*y**2 - y*z
Rest davon bei Division durch G = 0
Berechne S(x**2*y - z, x*z - y**2) = x*y**3 - z**2
Rest davon bei Division durch G = x*y**3 - z**2
Erhalte neues G = [-x**3 + y, x**2*y - z, x*z - y**2, x*y**3 - z**2]

Berechne S(-x**3 + y, x**2*y - z) = x*z - y**2
Rest davon bei Division durch G = 0
Berechne S(-x**3 + y, x*z - y**2) = x**2*y**2 - y*z
Rest davon bei Division durch G = 0
Berechne S(-x**3 + y, x*y**3 - z**2) = x**2*z**2 - y**4
Rest davon bei Division durch G = 0
Berechne S(x**2*y - z, x*z - y**2) = x*y**3 - z**2
Rest davon bei Division durch G = 0
Berechne S(x**2*y - z, x*y**3 - z**2) = x*z**2 - y**2*z
Rest davon bei Division durch G = 0
Berechne S(x*z - y**2, x*y**3 - z**2) = -y**5 + z**3
Rest davon bei Division durch G = -y**5 + z**3
Erhalte neues G = [-x**3 + y, x**2*y - z, x*z - y**2, x*y**3 - z**2, -y**5 + z**3]

Berechne S(-x**3 + y, x**2*y - z) = x*z - y**2
Rest davon bei Division durch G = 0
Berechne S(-x**3 + y, x*z - y**2) = x**2*y**2 - y*z
Rest davon bei Division durch G = 0
Berechne S(-x**3 + y, x*y**3 - z**2) = x**2*z**2 - y**4
Rest davon bei Division durch G = 0
Berechne S(-x**3 + y, -y**5 + z**3) = x**3*z**3 - y**6
Rest davon bei Division durch G = 0
Berechne S(x**2*y - z, x*z - y**2) = x*y**3 - z**2
Rest davon bei Division durch G = 0
Berechne S(x**2*y - z, x*y**3 - z**2) = x*z**2 - y**2*z
Rest davon bei Division durch G = 0
Berechne S(x**2*y - z, -y**5 + z**3) = x**2*z**3 - y**4*z
Rest davon bei Division durch G = 0
Berechne S(x*z - y**2, x*y**3 - z**2) = -y**5 + z**3
Rest davon bei Division durch G = 0
Berechne S(x*z - y**2, -y**5 + z**3) = x*z**4 - y**7
Rest davon bei Division durch G = 0
Berechne S(x*y**3 - z**2, -y**5 + z**3) = x*z**3 - y**2*z**2
Rest davon bei Division durch G = 0

Wir haben also eine GB gefunden: [-x**3 + y, x**2*y - z, x*z - y**2, x*y**3 - z**2, -y**5 + z**3]

In [11]:

    

reduce_groebner(G)


    

    
Out[11]:





[x**3 - y, x**2*y - z, x*z - y**2, x*y**3 - z**2, y**5 - z**3]

In [12]:

    

P, (x, y) = xring('x,y', QQ, lex)
G = [x**2 + 2*y**2 - 2, x**2 + x*y + y**2 - 2]


    

In [13]:

    

gt.groebner(G, P)


    

    
Out[13]:





[x**2 + 2*y**2 - 2, x*y - y**2, y**3 - 2/3*y]