Algorithme de Buchberger
Pour les articles homonymes, voir 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 ; un ordre monomial Sortie : une base de Gröbner de Répéter Pour chaque paire dans : reste de par Si est différent de 0 alors Jusqu'à ce que Renvoyer
Le polynôme dans l'algorithme est appelé -polynôme de et , parfois noté . 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
- ↑ (en) Bruno Buchberger, « Theoretical Basis for the Reduction of Polynomials to Canonical Forms », ACM SIGSAM Bulletin, vol. 10, no 3, , 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, , 3e éd. (lire en ligne), p. 83 et 90.
Article connexe
- Portail de l'informatique théorique
- Portail de l’algèbre