Ausgeführtes Beispiel für den Buchberger-Algorithmus



In [1]:

    
from sympy import *
init_printing()

Zuerst wird ein Polynomring geschaffen. QQ ist $\mathbb Q$. Alternative Termordnungen sind grlex und grevlex.



In [2]:

    
P, erzeuger = xring('x,y', QQ, lex)
x, y = erzeuger



In [3]:

    
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



In [4]:

    
f1 = x*y**2-x
f2 = x - y**3
G = [f1, f2]
G









    Out[4]:





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



In [5]:

    
s = S_poly(f1, f2)
s









    Out[5]:





-x + y**5



In [6]:

    
s.div(G)









    Out[6]:





([0, -1], y**5 - y**3)



In [7]:

    
f3 = s.div(G)[1]
f3









    Out[7]:





y**5 - y**3



In [8]:

    
G.append(f3)
S_poly(f1, f3)









    Out[8]:





$$0$$



In [9]:

    
s = S_poly(f2, f3)
s









    Out[9]:





x*y**3 - y**8



In [10]:

    
s.div(G)









    Out[10]:





([y, y, -y**3 - y], 0)



In [11]:

    
G









    Out[11]:





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

Es gibt auch zwei Funktionen, welche die reduzierte Gröbner-Basis direkt bestimmen. Zuerst die Funktion für den Fall, dass die Variablen wie oben einem vorab definierten Polynomring angehören.



In [12]:

    
from sympy.polys import groebnertools as gt



In [13]:

    
gt.groebner(G, P)









    Out[13]:





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

Die zweite Funktion akzeptiert Polynome aus Symbolen. Hier muss man die Termordnung explizit angeben. Wenn alle Koeffizienten ganz sind, arbeitet der Algorithmus über $\mathbb Z$; eine Gröbner-Basis über $\mathbb Z$ ist i.a. über $\mathbb Q$ nicht reduziert. Diese Funktion ist durch den allgemeinen import in der ersten Zeile bereits geladen.



In [14]:

    
x = Symbol('x')
y = Symbol('y')
f1 = 3*x*y**2-x
f2 = x - y**3
f1, f2









    Out[14]:





$$\left ( 3 x y^{2} - x, \quad x - y^{3}\right )$$



In [15]:

    
G = groebner([f1, f2], x, y, order='lex')
G









    Out[15]:





$$GroebnerBasis([x - y**3, 3*y**5 - y**3], x, y, domain='ZZ', order='lex')$$



In [16]:

    
G.polys









    Out[16]:





$$\left [ \operatorname{Poly}{\left( x - y^{3}, x, y, domain=\mathbb{Z} \right)}, \quad \operatorname{Poly}{\left( 3 y^{5} - y^{3}, x, y, domain=\mathbb{Z} \right)}\right ]$$

Achtung: Die Klasse Poly ist wieder eine andere Klasse.



In [ ]: