Modélisation de mécanismes et Algorithmes incrémentaux de Calcul des Bases de Gröbner.

Stage de Master M2

L’un des axes de recherche prioritaire de l’équipe POLSYS (INRIA/UPMC) est le calcul efficace des bases de Gröbner pour la résolution des systèmes polynomiaux. L’équipe Ingénierie Numérique du LISMMA (Supméca) est spécialisée dans l’étude des systèmes mécaniques. Les méthodes algébriques sont utilisées dans de nombreuses applications (mécanismes, robotique, cryptographie, …) et l’efficacité des algorithmes est primordiale pour mener à bien les calculs.

Pour l’étude de certains mécanismes (conditions de mobilité et d’assemblage par exemple) il s’agit dans un premier temps de les modéliser par des équations polynomiales. Chacune de ces équations fait intervenir des variables de positions et des paramètres (ou encore variables d’usinage). Dans un deuxième temps, on utilise des algorithmes de calcul des bases de Gröbner pour éliminer les variables de positions afin d’obtenir des expressions algébriques ne dépendant que des paramètres.

Le stage proposé s’inscrit dans un projet de recherche collaboratif établi entre Dassault-Systèmes, l’équipe POLSYS et le LISMMA.

Les objectifs du stage sont les suivants :

· Comparer l’efficacité des techniques de résolution algébrique pour différentes modélisations d’un même mécanisme. Par exemple on pourra comparer une modélisation classique [3] avec la modélisation de D. Lazard ou une modélisation utilisant des quaternions duaux.

· Proposer des versions tronquées des algorithmes existants (F4 ou F5) qui permettent d’arrêter prématurément les calculs (lorsqu’on a produit assez d’équations en les paramètres on peut stopper le calcul).

· Implanter des prototypes de ces algorithmes ainsi que les modélisations dans un système de Calcul Formel comme Maple.

[1] Jean-Charles Faugère. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139(1-3):61-88, June 1999.

[2] Jean-Charles Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In Proceedings of the 2002 international symposium on Symbolic and algebraic computation, ISSAC '02, pages 75-83, New York, NY, USA, 2002. ACM.

[3] P. Serré, A. Clément, A. Riviere. Vers une approche déclarative en CFAO. Application au mécanisme de Bennett 4th International Conference on Integrated Design and Manufacturing in Mechanical Engineering (IDMME 2002), Clermont-Ferrand (France), May 14-16, 2002

Contacts: Jean-Charles Faugère (INRIA) et Philippe Serré (LISMMA)