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},...,f_{s})$ ; 
          un ordre monomial 
Sortie : une base de Gröbner de  $\langle f_{1},...,f_{s}\rangle$ 

 $G\leftarrow F$ 
Répéter
      $G'\leftarrow G$ 
     Pour chaque paire  $\{p,q\}$  dans  $G'$ :
         $m\leftarrow lcm(LM(p),LM(q))$ 
        
         $S\leftarrow LC(p){\frac {m}{LM(p)}}p-LC(q){\frac {m}{LM(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)$ .

Références

↑ (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., 553 p. (ISBN 978-0-387-35651-8, BNF 44642535, présentation en ligne).

Article connexe

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., 553 p. (ISBN 978-0-387-35651-8, BNF 44642535, présentation en ligne).

[1]

[2]