Algorithme de Buchberger

Pour les articles homonymes, voir Buchberger.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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