logo EDITE Sujets de doctorat

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

Sujet proposé par
Directeur de thèse:
Encadré par
Doctorant: Ivan BANNWARTH
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

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. Les méthodes de résolution 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. Dans la plupart des applications visées, la résolution des systèmes polynomiaux doit se faire sur les réels : il s’agit le plus souvent de calculer des informations sur l’ensemble des solutions réelles d’un système polynomial. L'objectif de cette these est de concevoir et implanter des algorithmes conciliant compelxite asymptotique optimale et bonnes performances pratiques.

Enjeux

Pour l'heure, il n'existe aucune implantation d'algorithmes efficaces permettant de calculer la dimension (i.e. le nombre de degrés de liberté pour se déplacer sur le lieu-solution) ou effectuer des tests de connexité sur l'ensemble des solutions réelles d'un système d'équations polynomiales. De plus, les meilleurs algorithmes théoriques connus utilisent des techniques connues pour ne donner aucun bon résultat en pratique. Il s'agit donc d'un véritable défi que d'obtenir des algorithmes de complexité asymptotiquement optimale et pouvant déboucher sur des implantations rapides en pratique. Ceci est crucial pour diverses applications en mécanique ou robotique qui ont déjà été identifiées.

Ouverture à l'international

Cette these sera développée dans le cadre d'une collaboration de longue date avec le département d'informatique de Univ. of Western Ontario au Canada (avec E. Schost).

E. Schost sera d'ailleurs Professeur Invité à l'automne prochain au Laboratoire d'Informatique de Paris 6 et pourra participer au lancement de cette thèse.

De plus, des collaborations pourraient voir le jour dans le cadre de cette thèse avec le département d'ingénierie de l'Université de Détroit aux États-Unis.