Ensembles triangulaires de polynômes et résolution de systèmes algébriques

Ph. Aubry

LIP6 2001/008: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
171 pages - Janvier/January 1999 - French document.

Get it : 1166 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Calcul Formel

Titre français : Ensembles triangulaires de polynômes et résolution de systèmes algébriques
Titre anglais : Polynomial triangular sets and algebraic systems solving

Résumé : La première partie de cette thèse présente une étude des propriétés de différentes notions d'ensembles triangulaires de polynômes et des algorithmes sous-jacents qui permettent de résoudre symboliquement les systèmes d'équations algébriques. Nous montrons en particulier l'équidimensionnalité pure du saturé d'un ensemble triangulaire, et en déduisons ensuite l'équivalence de notre notion simple d'ensemble triangulaire régulier avec celle de chaîne régulière. Nos nouveaux algorithmes permettent des décompositions triangulaires de systèmes polynomiaux plus efficaces et des spécifications plus fortes.
La seconde partie traite de théorie de Galois algébrique constructive par une nouvelle approche. Nous montrons avec A. Valibouze qu'un idéal de Galois d'un polynôme séparable f associé à un groupe de permutations contenant le groupe de Galois de f, est engendré par une base de Groebner triangulaire. Grâce à ce résultat de structure, nous développons de nouveaux algorithmes (calcul de résolvantes relatives et de générateurs d'un idéal de Galois).
La troisième partie est consacrée aux aspects d'implantation, d'expérimentation et applicatifs. Nous présentons un travail de comparaison expérimentale de quatre méthodes de décomposition triangulaire réalisé avec M. Moreno Maza, puis donnons trois exemples d'applications de nos implantations (idéal de Galois d'un polynôme, compression d'images, problème des n corps).

Abstract : In the first part of this thesis, we study the properties of differents notions of triangular polynomial sets and we present corresponding algorithms for the symbolic resolution of algebraic systems. We show in particular the pure equidimensionality of the saturate of a triangular set, and then deduce the equivalence of our simple notion of regular triangular set with the concept of regular chain. Our new algorithms allows more efficient triangular decompositions of polynomial systems and stronger specifications.
The second part treats constructive algebraic Galois theory by a new approach. We show with A. Valibouze that a Galois ideal of a separable polynomial f associated with a permutations group which contains the Galois group of f, is generated by a triangular Groebner basis. We develop new algorithms from this structure result (computation of relative resolvents and generators of Galois ideals).
The third part is devoted to implementation, experimentation and applications. We present a work of experimental comparison on four methods for computing triangular decompositions realized with M. Moreno Maza, then we give three applications of our implementations (Galois ideal of a polynomial, image compression, n body problem).

Mots-clés : calcul formel, ensemble triangulaire, systèmes polynomiaux, théorie de Galois, Groebner, décomposition équidimensionnelle

Key-words : computer algebra, triangular set, polynomial systems, Galois theory, Groebner, equidimensional decomposition

Publications internes LIP6 2001 / LIP6 research reports 2001

Responsable Éditorial / Editor :David.Massot@lip6.fr