Return to search

Complexité des représentations des systèmes de polynômes : triangulation, méthodes modulaires, évaluation dynamique.

Les systèmes polynomiaux sous forme triangulaire, notamment les chaînes régulières et en particulier les ensembles triangulaires (de Lazard), sont des structures de données simples, permettant d'envisager des calculs modulaires (par spécialisation des coefficients, puis remontée via un opérateur de Newton-Hensel), de "résoudre'' les systèmes de polynômes (méthodes de "triangulations'') et de représenter des tours d'extensions de corps pour calculer avec les nombres algébriques. Dans ces trois domaines, les méthodes et résultats nouveaux apportés, notamment sur le plan de la complexité, étendent le champs d'application des ensembles triangulaires, et leur impact face à d'autres méthodes de manipulation des équations polynomiales, surtout les bases de Gröbner. Tout d'abord la complexité en espace des coefficients n'est qu'en croissance quadratique en fonction de données géometriques naturelles. Conséquence directe en est un opérateur de Newton (triangulaire) requérant moins d'étapes de remontée, et donc des méthodes modulaires plus encourageantes. Il en est ainsi pour la décomposition équiprojetable, premier algorithme de triangulation des systèmes basé sur une méthode modulaire, et pour le problème du changement d'ordres monomiaux en dimension positive, dans des cas assez particuliers toutefois pour une première approche. Par ailleurs, calculer modulo un ensemble triangulaire en suivant le modèle de l'évaluation dynamique, se voit doté, 20 ans après sa création, d'un premier résultat de complexité satisfaisant.

Identiferoai:union.ndltd.org:CCSD/oai:pastel.archives-ouvertes.fr:pastel-00003835
Date24 November 2006
CreatorsDahan, Xavier
PublisherEcole Polytechnique X
Source SetsCCSD theses-EN-ligne, France
LanguageEnglish
Detected LanguageFrench
TypePhD thesis

Page generated in 0.002 seconds