Modlisation de mcanismes et Algorithmes incrmentaux de
Calcul des Bases de Grbner.
Stage de Master M2
LĠun des axes de recherche prioritaire de lĠquipe POLSYS (INRIA/UPMC) est le calcul efficace
des bases de Grbner
pour la rsolution des systmes polynomiaux. LĠquipe Ingnierie Numrique du
LISMMA (Supmca) est spcialise dans lĠtude des
systmes mcaniques. Les mthodes algbriques sont utilises dans de nombreuses
applications (mcanismes, robotique, cryptographie, É)
et lĠefficacit des algorithmes est primordiale pour mener bien les calculs.
Pour lĠtude de certains
mcanismes (conditions de mobilit et dĠassemblage par exemple) il sĠagit dans
un premier temps de les modliser par des quations polynomiales. Chacune de
ces quations fait intervenir des variables de positions et des paramtres (ou
encore variables dĠusinage). Dans un deuxime temps, on utilise des algorithmes
de calcul des bases de Grbner pour liminer
les variables de positions afin dĠobtenir des expressions algbriques ne
dpendant que des paramtres.
Le stage propos sĠinscrit
dans un projet de recherche collaboratif tabli entre Dassault-Systmes, lĠquipe
POLSYS et le LISMMA.
Les objectifs du stage
sont les suivants :
á Comparer lĠefficacit des techniques de
rsolution algbrique pour diffrentes modlisations dĠun mme mcanisme. Par
exemple on pourra comparer une modlisation classique [3] avec la modlisation
de D. Lazard ou une modlisation utilisant des quaternions duaux.
á Proposer des versions tronques des
algorithmes existants (F4 ou F5) qui permettent dĠarrter prmaturment les
calculs (lorsquĠon a produit assez dĠquations en les paramtres on peut
stopper le calcul).
á Implanter des prototypes de ces algorithmes
ainsi que les modlisations dans un systme de Calcul Formel comme Maple.
[1] Jean-Charles
Faugre. A new efficient algorithm
for computing Grbner bases (F4). Journal of Pure
and Applied Algebra,
139(1-3):61-88, June 1999.
[2] Jean-Charles
Faugre. A new efficient algorithm
for computing Grbner 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. Clment, A. Riviere. Vers une approche
dclarative en CFAO. Application au mcanisme
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
Faugre (INRIA) et Philippe Serr (LISMMA)