Quelques Approches Algorithmiques Pour Les Polynômes

Résumé: Le but de ce travail est d'étudier quelques approches algorithmiques pour les polynômes. Le calcul formel calcule des objets mathématiques exacts, et repose de manière naturelle sur des constructions algébriques qui préservent la décidabilité du test à 0. En particulier, les opérations courantes sur les vecteurs, matrices, polynômes, fractions rationnelles, ne nécessitent pas d'autres test à 0 que celui des coefficients. Les polynômes peuvent être représentés de plusieurs manières, et la meilleure représentation dépende des opérations que l'on souhaite effectuer pour un polynôme à une variable. Les choix principaux sont : - la représentation dense. - la représentation creuse. De même, les fractions rationnelles sont représentées par des paires de polynômes. Les opérations d'addition, produit, division, se réduisent aux additions et multiplications sur les coefficients. Des réponses peuvent être obtenues algorithmiquement. La complexité donne ensuite des outils pour comparer des algorithmes du point de vue de leur efficacité. La multiplication des polynômes est omniprésente: Les algorithmes de calcul de pgcd, de pgcd étendu, de factorisation en une ou plusieurs variables, de composition des séries formelles, d'évaluation multipoint, d'interpolation, font tous intervenir des produits de polynômes. L'analogie entre les entiers et les polynômes va très loin; la plupart des réponses apportées dans le cadre de complexité arithmétique trouvent un équivalent en complexité binaire. Cependant, aucun théorème d'équivalence n'est connu; il se trouve que les mêmes idées algorithmiques s'adaptent plus ou moins facilement dans les deux cadres. Ainsi, on dispose des résultats dans le modèle binaire.

Publié dans la revue: