Topologie des courbes et surfaces singulières – SingCAST

Au cours de 18 premiers mois du projet, nous avons travaillé principalement sur le problème d'approximation de courbe par une courbe linéaire par morceaux avec la même topologie. Nous nous sommes restreint spécifiquement au cas des courbes singulières 2D définies comme la projection de courbe lisse 3D. Dans ce cas, nous avons conçu un nouvel algorithme d'isolation des points singuliers d'une courbes 2D, nous l'avons implanté, et nous avons montré son efficacité par rapport à l'état de l'art.

En particulier, étant donné P(x,y,z) et Q(x,y,z) deux polynômes de degré d, nous nous sommes concentré sur le cas d'une courbe C défini comme l'ensemble des points réels (x,y) tels que il existe z solution des équations P(x,y,z) = Q(x,y,z) = 0. En pratique, les approches dans l'état de l'art permettent le calcul de points singuliers pour d inférieur à 10. Notre nouvel méthode permet d'isoler les points singuliers jusqu'à d=12. De plus nous avons étendu notre travail au cas des fonctions analytiques et nous avons développé une nouvelle méthode pour calculer les singularités de C dans le cas où P et Q sont des fonctions analytiques, i.e. l'expansion de Taylor de P et Q converge en tout point. À notre connaissance, nous avons conçu le premier algorithme permettant d'isoler et de certifier les singularités d'une courbe analytique singulière définie comme la projection d'une courbe analytique lisse.

Nous avons conçu le premier algorithme isolant et certifiant les singularités d'une famille de courbe analytiques singulières.

Notre travail sur les courbes nous a pris plus de temps que prévu, mais les résultats ont dépassé nos attentes, notamment grâce à l'aide d'un étudiant post-doctoral recruté avec le financement de l'ANR. De plus, nous avons maintenant des idées plus précises pour traiter les surfaces singulières définies comme la projection en (x,y,z) de surfaces lisse 4D définies implicitement par des équations de la forme P(x,y,s,t) = Q(x,y,z,t) = 0. Les résultats que nous avons obtenus sur les fonctions analytiques sont aussi très encourageant. En particulier, cela devrait nous permettre de décrire précisément des mécanismes robotiques comme le 3-RRR par exemple, pour lequel aucune description rigoureuse n'existe dans l'état de l'art.

D'un point de vue implantation, nos outils sont développés en partie en python et en partie en C++. Cela nous permettra facilement d'inclure notre bibliothèque de visualisation dans le système de calcul formel sage. Avec le temps et les ressources nécessaires, nous evisageons aussi éventuellement de porter nos outils en C/C++ pour faciliter leur intégration dans un autre système de calcul formel.

Notre travail a donné lieu à deux articles soumis respectivement dans une revue et une conférence internationales, listées ci-dessous. Nous avons aussi écrit un premier prototype de logiciel en python et C++ permettant d'isoler les singularités de la projection d'une courbe algébrique lisse.

[1] R. Imbach, G. Moroz, M. Pouget. Numeric certified algorithm for the topology of resultant and discriminant curves, submitted to Journal of Symbolic Computation.

[2] R. Imbach, G. Moroz, M. Pouget. Numeric and Certified Isolation of the Singularities of the Projection of a Smooth Space Curve, submitted to MACIS 2015.

De nombreuses applications en calcul scientifique peuvent être modélisées par des systèmes polynomiaux. La plupart des informations sur le problème initial sont donc codées dans l'ensemble des solutions de tels systèmes. Dans les exemples les plus simples, les solutions sont un ensemble fini de points, mais pour modéliser des applications plus complexes, plus de variables et de contraintes sont nécessaires et l'ensemble des solutions peut être une courbe, une surface ou un objet de dimension supérieure. Certaines applications, telles que la robotique ou la visualisation, nécessitent une description de l'ensemble des solutions avec des garanties. On peut distinguer deux types de garanties: topologique, toutes les composantes et toutes les singularités (points isolés ou auto-intersections) doivent être détectées; géométrique, l'ensemble des solutions doit être approché à une distance donnée.

Théoriquement, les méthodes symboliques algébriques peuvent garantir la topologie de tout système polynomial grâce aux résultants, bases de Gröbner ou décompositions cylindriques algébriques. Cependant, la grande complexité de ces méthodes purement algébriques les empêche d'être appliquées dans la pratique sur des cas difficiles. D'autre part, les méthodes purement numériques telles que l'arithmétique d'intervalles ou les subdivisions, sont efficaces dans la pratique pour des ensembles de solutions non singuliers, mais manquent de garanties topologiques près des points singuliers. Cette question est un défi de longue date dans la communauté du calcul numérique.

Cette exposition des forces et faiblesses des méthodes symboliques/numériques plaide en faveur d'une nouvelle approche combinant ces méthodes. L'objectif de notre projet est de mêler les approches symboliques et numériques pour calculer efficacement les ensembles de solutions de systèmes polynomiaux avec des garanties topologiques et géométriques dans le cas singulier. Techniquement, nous allons explorer l'utilisation des propriétés algébriques locales (anneaux locaux de singularités) et de l'arithmétique d'intervalle (opérateur Krawczyk) pour isoler les singularités. Nos nouveaux critères de certification des singularités seront locaux et amélioreront naturellement les algorithmes basés sur des subdivisions et les algorithmes basés sur le suivi (homotopie). Nous sommes conscients de la complexité des systèmes polynomiaux généraux. Ainsi, l'un des objectifs est d'identifier des classes de problèmes avec des types restreints de singularités et de développer des méthodes dédiées qui tirent parti de la structure des systèmes polynomiaux associés. Nous nous concentrons sur deux applications: la visualisation des courbes et des surfaces algébriques et la conception mécanique des robots. Nous prévoyons d'étendre la classe des manipulateurs qui peuvent être analysés, et la classe des courbes et surfaces qui peuvent être visualisées avec certification.

Les partenaires du projet sont choisis pour la complémentarité de leurs expertises. Guillaume Moroz est un expert de calcul formel et a développé le package Maple RootFinding[Parametric] et des outils spécifiques pour la robotique (ANR SIROPA 2007-2011). Marc Pouget est un expert de la topologie et la géométrie des courbes et des surfaces et a développé des logiciels de visualisation (CGAL et Isotop). G. Moroz et M. Pouget sont membres de l'équipe INRIA VEGAS, G. Moroz est nouveau dans l'équipe et renforce le thème de la géométrie algorithmique non-linéaire de VEGAS. Nous avons également deux équipes de collaborateurs externes. Joris Van Der Hoven et Grégoire Lecerf sont des experts en calculs numériques et symboliques et des systèmes de calcul formel (Mathemagix). Enfin, Philippe et Damien Wenger Chablat, l'équipe de robotique à l'IRCCyN valideront nos méthodes grâce à nos logiciels prototypes.