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[1].

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

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

1. (en) Bruno Buchberger, « Theoretical Basis for the Reduction of Polynomials to Canonical Forms », ACM SIGSAM Bulletin, vol. 10, n^o 3,‎ août 1976, p. 19-29.
2. (en) David A. Cox, John Little et Don O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, New York, Springer-Verlag, 2007, 3^e éd. (lire en ligne), p. 83 et 90.

Article connexe

Complétion de Knuth-Bendix