Complexity of polynomial systems representations: triangulation, modular methods, dynamic evaluation.
Complexité des représentations des systèmes de polynômes : triangulation, méthodes modulaires, évaluation dynamique.
Résumé
The polynomial systems in their triangular shape, notably the regular chains and especially the Lazard triangular sets, are simple data structures, permitting to consider modular computations (by specialization of the coefficients, then lifting through the Newton-Hensel operator), to "solve'' the polynomial systems ("decomposition-triangulations'' methods) and to represent tours of fields extensions to compute with algebraic numbers. For those three topics, the methods and results provided here, notably on the complexity front, extend the fields of applications of triangular sets, and their impact compared to other methods of manipulation of algebraic equations, especially the Gröbner bases. First of all the space complexity of the coefficients is only on quadratic growth in function of natural geometric data. Straightforward corollary is a (triangular) Newton operator requiring less lifting steps, hence more promising modular methods. So it is for the equiprojectable decomposition}, first polynomial systems triangulation algorithm based on a modular method, and for the problem of the change of monomials orderings in positive dimension, yet in some quite specific cases for a first approach. In addition, computing modulo a triangular set by following the dynamic evaluation model, is now endowed, 20 years after its apparition, of a first satisfaying complexity study.
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.
Loading...