BANNWARTH Ivan

Doctorant
Équipe : PolSys
Date d'arrivée : 01/09/2014
Localisation : Jussieu
    UPMC - LIP6
    Boîte courrier 169
    Couloir 26-00, Étage 3, Bureau 338
    4 place Jussieu
    75252 PARIS CEDEX 05
Tel: 01 44 27 71 30, Ivan.Bannwarth (at) nulllip6.fr
Direction de recherche : Mohab SAFEY EL DIN

Algorithmes rapides pour la topologie des ensembles semi-algébriques, Implantations et Applications

La résolution des systèmes polynomiaux est un problème central en Calcul Formel du fait de ses nombreuses applications dans de nombreux domaines des sciences de l’ingénierie (sciences physiques, biologie, chimie, robotique) et des sciences informatiques (cryptologie, géométrie algorithmique, vision, etc). Les méthodes de résolutions algébriques ont déjà montré leur intérêt dans divers domaines d’applications des sciences de l’ingénieur comme la robotique, la biologie, la médecine, etc, qui constituent les champs d’application de cette thèse. La problématique centrale est d’obtenir des algorithmes et des implantations conciliant complexité théorique asymptotiquement optimale et efficacité pratique pour calculer des informations sur la topologie des ensembles de solutions réelles de systèmes polynomiaux (que nous appelons ensembles semi-algébriques). En effet, dans la plupart des applications visées, la résolution des systèmes polynomiaux doit se faire sur les réels et les informations requises sur les ensembles semi-algébriques sont diverses et variées. Souvent, le calcul de ces informations est significativement plus difficile que l’obtention d’informations similaires sur l’ensemble des solutions complexes. Ainsi, il a fallu attendre les années 70 pour voir apparaître un algorithme (Décomposition Cylindrique Algébrique) de complexité élémentairement récursive permettant d’étudier les solutions réelles d’un système d’équations polynomiales [Collins75]. Cet algorithme de Décomposition Cylindrique Algébrique est néanmoins de complexité doublement exponentielle en le nombre de variables. Cette complexité élevée provient du fait que l’algorithme calcule un objet exhaustif (de taille doublement exponentielle) permettant de décrire la topologie complète de l’ensemble semi-algébrique étudié. La contre-partie est évidemment que les logiciels fondés sur ces techniques ont des performances pratiques limitées aux problèmes non triviaux en 3 ou 4 variables. C’est largement insuffisant pour de nombreuses applications. À la fin des années 80, une nouvelle famille d’algorithmes apparaît. Plutôt que de calculer un objet fournissant une représentation exhaustive des semi-algébriques, l’idée est d’obtenir des algorithmes spécialisés, ayant une sortie plus faible mais avec l’espoir d’obtenir des meilleures complexités. C’est ainsi que pour les systèmes de s polynômes de degré D en n variables, le calcul d’au moins un point par composante connexe dans le semi-algébrique se fait en temps essentiellement (sD)^O(n); les tests de connexité et le calcul de la dimension réelle se font en temps essentiellement (sd)^O(n^2). On est donc passé d’une complexité doublement exponentielle à des complexités simplement exponentielles (voir [Basu10]). Néanmoins ces progrès n’ont pas permis d’aboutir à des implantations plus performantes que celles de l’algorithme de Décomposition. Ceci est essentiellement dû au fait que les constantes situées en exposant sont trop élevées. Au début des années 2000, de nouvelles pistes de recherche ont été explorées pour diminuer significativement ces constantes de complexité. Ceci a débouché sur divers algorithmes et des progrès spectaculaires pour le calcul d’au moins un point par composante connexe dans des semi-algébriques [Safey07,Safey03, Hong12, Faugère08]. Le logiciel actuel fondé sur ces méthodes permet de résoudre des systèmes qu’on n’imaginait pas résoudre il y a une dizaine d’années. Il faut donc maintenant suivre la même trajectoire pour le calcul de la dimension réelle d’un semi-algébrique (i.e. calculer le nombre de degrés de liberté avec lequel on peut se mouvoir sur l’ensemble considéré) ou des tests de connexité. Même si il semble que les complexités théoriques peuvent encore être améliorées [Safey13], bon nombre des techniques utilisées dans [Safey07,Safey03, Hong12, Faugère08] pourraient permettre d’obtenir un meilleur contrôle sur les constantes situées en exposant. Plus précisément, il n’existe pas à l’heure actuelle d’implantations compétitives en pratique d’algorithmes de complexité (sD)^O(n^2) pour le calcul de la dimension réelle d’un ensemble semi-algébrique. Un premier objectif est d’utiliser les techniques présentées dans [Safey03, Hong12] pour réduire les constantes de complexité en exposant. En effet, ces techniques permettraient de calculer les frontières de projections des semi-algébriques étudiés. Une fois ces projections calculées, il suffit ensuite de calculer au moins un point par composante connexe dans le complémentaire de ces frontières pour déterminer si ces projections sont d’intérieur non vides. Pour ce dernier calcul on s’appuiera sur le logiciel RAGlib qui implante lui aussi des algorithmes de complexité simplement exponentielle. In fine, nous espérons l’obtention d’algorithmes dont les implantations sont plus efficaces de plusieurs ordres de grandeur que celles de la Décomposition Cylindrique Algébrique. Ces implantations seront confrontées à des applications importantes en mécanique où il s’agit de déterminer les paramètres d’un système lui conférant le plus de mobilité possible. Une piste de recherche plus théorique et plus risquée consiste à s’appuyer sur des propriétés intrinsèques des objets étudiés dans [Bank10] pour obtenir des algorithmes de calcul de la dimension d’un ensemble semi-algébrique en temps D^O(n). Un deuxième problème particulièrement important relié à la topologie des ensembles semi-algébriques consiste à effectuer des tests de connexité. Plus précisément, étant donnés deux points dans un ensemble semi-algébrique, le problème consiste à déterminer si il existe un chemin continu dans l’ensemble semi-algébrique permettant de relier ces deux points. Pour résoudre ce problème, on commence par calculer une carte routière : il s’agit d’une courbe contenant ces deux points et ayant une intersection connexe et non vide avec chaque composante du semi-algébrique considéré. Ainsi, on réduit les tests de connexité en dimension arbitraire à des tests de connexité en dimension 1. Très récemment des algorithmes de complexité essentiellement O((sD)^(6nlog(n))) ont été fournis pour le calcul de cartes routières [Safey13] sous certaines hypothèses. Des premiers tests expérimentaux montrent le potentiel de ces nouvelles approches. Néanmoins il n’existe aucune implantation permettant d’effectuer efficacement ces tests de connexité en dimension 1. Il s’agit donc maintenant de développer des algorithmes rapides pour ces tests. Toujours en exploitant les propriétés des objets manipulés dans [Bank10, Safey13] on espère aboutir à des algorithmes essentiellement cubiques en le degré des cartes routières calculées. On envisagera également l’exploitation d’informations préalablement obtenues par le calcul de cartes routières pour accélérer ces tests de connexité. Diverses applications seront étudiées.
[Bank21] B. Bank, M. Giusti, J. Heintz, M. Safey El Din, and É. Schost. On the geometry of polar varieties. Applicable Algebra in Engineering, Communication and Computing, 2010.
[Basu06] S. Basu, R. Pollack, and M.-F. Roy. Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, second edition, 2006.
[Collins75] G. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In Automata Theory and Formal Languages, pages 134–183. Springer, 1975.
[Faugère08] J.-C. Faugère, G. Moroz, F. Rouillier, and M. Safey El Din. Classification of the perspective three-point problem, discriminant variety and real solving polynomial systems of inequalities. In Proceedings of ISSAC 2008, pages 79–86, 2008.
[Hong12] H. Hong and M. Safey El Din. Variant quantifier elimination. J. Symb. Comput., 47(7) :883–901, July 2012.
[Safey03] M. Safey El Din and É. Schost. Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In ISSAC’03, pages 224–231. ACM, 2003.
[Safey07] M. Safey El Din. Testing sign conditions on a multivariate polynomial and applications. Mathematics in Computer Science, 1(1) :177–207, December 2007.
[Safey13] M. Safey El Din and E. Schost. A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. arXiv preprint arXiv :1307.7836, 2013.

Publications 2015

 Mentions légales
Carte du site |