Projet ANR-13-JS02-0006 – SingCAST : Topologie des courbes et surfaces singulières
Programme : JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2) 2013
Année de financement : 2013
Coordinateur du projet : Monsieur Guillaume MOROZ (INRIA Nancy Grand Est)
Partenaires : Inria Centre Nancy - Grand Est
Montant : 96652.0 euros
Date de début : 2014
Durée : 42 mois
Résumé : 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.