Algorithme de Buchberger

Modèle:Voir homonymes Modèle:Ébauche 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 $F=(f_1,\dots ,f_s)$ ; 
          un ordre monomial 
Sortie : une base de Gröbner de $⟨f_1,\dots ,f_s⟩$

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

Le polynôme $S$ dans l'algorithme est appelé $S$-polynôme de $p$ et $q$, parfois noté $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).

Article connexe

Complétion de Knuth-Bendix