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

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

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

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

Références modifier

↑ (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.
↑ (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 modifier

Complétion de Knuth-Bendix

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

[1]

[2]