Algorithme de Buchberger

L'algorithme de Buchberger est un algorithme permettant de calculer une base de Gröbner pour un idéal polynomial à partir d'un ensemble générateur de l'idéal et d'un ordre sur les monômes. Il a été publié par le mathématicien autrichien Bruno Buchberger en 1976.

En pseudo-code, il peut être décrit comme suit :

Entrées : un système de polynômes ${\displaystyle F=(f_{1},\dots ,f_{s})}$ ; 
          un ordre monomial 
Sortie : une base de Gröbner de ${\displaystyle \langle f_{1},\dots ,f_{s}\rangle }$

${\displaystyle G\leftarrow F}$
Répéter
     ${\displaystyle G'\leftarrow G}$
     Pour chaque paire ${\displaystyle \{p,q\}}$ dans ${\displaystyle G'}$ :
        ${\displaystyle m\leftarrow \operatorname {ppcm} (\operatorname {MD} (p),\operatorname {MD} (q))}$
        
        ${\displaystyle S\leftarrow {\frac {m}{\operatorname {TD} (p)}}p-{\frac {m}{\operatorname {TD} (q)}}q}$ 
        
        ${\displaystyle r\leftarrow }$ reste de ${\displaystyle S}$ par ${\displaystyle G'}$
        Si ${\displaystyle r}$ est différent de 0 alors ${\displaystyle G\leftarrow G\cup \{r\}}$
Jusqu'à ce que ${\displaystyle G=G'}$
Renvoyer ${\displaystyle G}$

Le polynôme ${\displaystyle S}$ dans l'algorithme est appelé ${\displaystyle S}$-polynôme de ${\displaystyle p}$ et ${\displaystyle q}$, parfois noté ${\displaystyle S(p,q)}$. Les fonctions MD et TD sont respectivement le « monôme dominant » et le « terme dominant » (produit du monôme dominant par son coefficient).

Références

Article connexe

Complétion de Knuth-Bendix

• Portail de l'informatique théorique
• Portail de l’algèbre