Algorithme de Buchberger

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir 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 F = (f_1, ..., f_s); 
          un ordre monomial 
Sortie : une base de Gröbner de \langle f_1, ..., f_s\rangle

G \leftarrow F
G' \leftarrow G
Répéter
    Pour chaque paire \{p,q\} dans G':
        r \leftarrow reste de S(p,q) par G'
        Si r est différent de 0 alors G \leftarrow G \cup \{r\}
Jusqu'à ce que G=G'
Renvoyer G

Références[modifier | modifier le code]

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