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érence[modifier | modifier le code]

  1. Bruno Buchberger, Theoretical Basis for the Reduction of Polynomials to Canonical Forms. ACM SIGSAM Bulletin. 10 (3): 19–29. Août 1976.
  2. David Cox, John Little, and Donal O'Shea (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer. ISBN 0-387-94680-2.