Titre
Méthodes matricielles pour la résolution de
systèmes d'équations polynomiales.
Lieu
INRIA,
Projet SAFIR
2004 route des Lucioles, BP 93,
06902 Sophia Antipolis, France.
Information
Ioannis Z. Emiris :
emiris@sophia.inria.fr
Bernard Mourrain :
mourrain@sophia.inria.fr
tél: 93 65 78 28.
Description
Nous nous intéressons à la résolution de systèmes d'équations polynomiales et
aux applications de ces méthodes à la robotique et la vision. Parmi ces
méthodes, les approches basées sur des calculs matriciels
commencent à emmerger. Ces méthodes consistent à réduirent le problème de
résolution à un calcul de valeurs propres de matrices de multiplications.
Historiquement, ces techniques partent de travaux de Bézout, Sylvester,
Macaulay,... dans lesquels des algorithmes sont donnés explicitement
pour construire des matrices de multiplications par les variables. Ceci ne
s'applique cependant que pour des systèmes de polynômes, dits génériques.
Hélas les systèmes que l'on rencontre en pratique sont rarement
génériques (tous les monômes pour un degré donné n'apparaissent pas, il y a
une grosse composante à l'infini,...). Ceci a donc conduit à des études ne
prenant en compte que les monômes qui apparaissent dans les équations. d'autres méthodes sont actuellement à l'étude pour
permettant de construire des matrices ayant comme taille, exactement le nombre de solutions du système, tenant compte de la géométrie des monômes
et des relations qui existent entre les coefficients.
L'objectif de ce stage sera donc
- dans un premier temps, de faire un rapide tours d'horizon des méthodes matricielles et de se familirariser avec la bibliothéque
ALP.
- puis d'analyser et développer différents outils
permettant de construire les matrices utilisées dans la résolution des systèmes
polynomiaux,
- de tester ces outils sur des problèmes concrets (
configuration de molecules, robotique, reconstruction en vision, ...)
Ce sujet s'inscrit dans le cadre du projet européen FRISCO (LTR 21.024).
Il fait suite au stage proposé l'année dernière sur un sujet similaire et
étendra donc le travail déja fait.
Outils
Stations de travail SUN, DEC, PC Pentium pro 167, langage C++, système
de calcul formel Maple.
Durée
Au moins 3,6 mois. Il pourrait se poursuivre par une thèse.
Nous nous intéressons à la résolution de systèmes d'équations polynomiales et
aux applications de ces méthodes à la robotique et la vision. Parmi ces
méthodes, les approches basées sur des calculs matriciels
commencent à emmerger. Ces méthodes consistent à réduirent le problème de
résolution à un calcul de valeurs propres de matrices de multiplications.
Historiquement, ces techniques partent de travaux de Bézout, Sylvester,
Macaulay,... dans lesquels des algorithmes sont donnés explicitement
pour construire des matrices de multiplications par les variables. Ceci ne
s'applique cependant que pour des systèmes de polynômes, dits génériques.
Hélas les systèmes que l'on rencontre en pratique sont rarement
génériques (tous les monômes pour un degré donné n'apparaissent pas, il y a
une grosse composante à l'infini,...). Ceci a donc conduit à des études ne
prenant en compte que les monômes qui apparaissent dans les équations. d'autres méthodes sont actuellement à l'étude pour
permettant de construire des matrices ayant comme taille, exactement le nombre de solutions du système, tenant compte de la géométrie des monômes
et des relations qui existent entre les coefficients.