Approche géométrique de la complexité et applications

• SALVY Bruno
• BOSTAN Alin
• CHYZAK Frédéric
• VILLARD Gilles
• GALLIGO André
• BUSE Laurent
• ELKADI Mohamed
• MOURRAIN Bernard
• TECOURT Jean-Pierre
• LE Thi Ha
• GIUSTI Marc
• LECERF Grégoire
• LUC Christophe
• SCHOST Eric
• VAN DER HOEVEN Joris
• DAHAN Xavier
• DURVYE Clémence
• YAKOUBSOHN Jean-Claude
• AMODEI Lucas
• DEDIEU Jean-Pierre
• MASSIAS Henri
• RUATTA Olivier
• VOLERY Jean-Luc
• LIANG Kewei

Résumé du projet

Ce projet allie les compétences de quatre équipes reconnues de mathématiciens et d'informaticiens à la confluence de l'analyse numérique, des méthodes effectives en algèbre, du calcul formel, de la théorie de la complexité des algorithmes. Le développement scientifico-technologique de la société pose des problèmes qui, moyennant simplifications et modélisations, se traduisent fréquemment par des systèmes d'équations et d'inéquations algébriques ou différentielles, et nécessitent des solutions, c'est-à-dire des processus capables de les résoudre. Notre objectif est la conception de tels processus et l'étude de leurs performances. Son originalité réside dans une approche géométrique visant à exploiter les spécificités d'instances de problèmes au sein de leur classe. Sont visées principalement trois classes d'objets: (i) les polynômes en une ou plusieurs variables (processus de Newton, factorisation, élimination) ; (ii) les matrices structurées (dont les coefficients peuvent être des polynômes) ; (iii) les opérateurs différentiels linéaires (élimination non-commutative, intégration). Le but est d'améliorer significativement la résolution de systèmes d'équations et d'inéquations algébriques ou différentiels qui apparaissent dans des modélisations, en tenant compte de la géométrie. Nos algorithmes seront validés par des logiciels portables et distribués librement, développés avec en ligne de mire l'efficacité sur des problèmes de très grandes tailles.

Abstract

Four renowned teams of mathematicians and computer scientists are allied in this project at the meeting point of numerical analysis, effective methods in algebra, symbolic computation, complexity theory. The scientific and technological progress of our society raises problems that are often expressed, after simplification and modelization, in terms of systems of algebraic or differential equations and inequations, and that require a solving process. Our aim is to design such processes and study their performance. The originality lies in a geometric approach aiming at the exploitation of specific instances inside their class of problems. We will concentrate our efforts on three classes of objects: (i) univariate and multivariate polynomials (Newton process, factorization, elimination); (ii) structured matrices (whose coefficients can be polynomials); (iii) linear differential operators (noncommutative elimination, integration). Our aim is to improve significantly the resolution of systems of algebraic or linear differential equations that appear in models, by taking geometry into account. Our algorithms will be vindicated by software that will be portable and freely available, whose development will be targeted at efficiency on problems of very large size.