10h30: Multiples communs d'op�rateurs lin�aires diff�rentiels et � diff�rences. Fr�d�ric Chyzak, �quipe Algorithms, Inria Paris-Rocquencourt.

Abstract Le calcul du plus petit commun multiple de plus de deux op�rateurs lin�aires, diff�rentiels ou � diff�rences, intervient dans des probl�mes comme l'extraction de sous-s�ries de s�ries multi-sommables, en th�orie de la resommation, ou pour la sommation symbolique de fonctions rationnelles. Hormis dans ces quelques cas o� les op�rateurs dont on consid�re le p.p.c.m. sont tr�s structur�s, le p.p.c.m. d'op�rateurs lin�aires g�n�raux ne semble avoir �t� �tudi� que dans le cas restreint de deux op�rateurs, par une g�n�ralisation de la m�thode des sous-r�sultants. Par ailleurs, van der Hoeven a montr� en 2000 comment le produit d'op�rateurs diff�rentiels lin�aires g�n�raux (en caract�ristique nulle) se ram�ne au produit de matrices. Tout r�cemment, Bostan, Chyzak et Le Roux ont m�me montr� l'�quivalence des deux probl�mes en complexit� (toujours en caract�ristique nulle). Il devient ainsi tout naturel, � l'imitation du cas commutatif, de prendre pour �talon le co�t du produit de matrices et d'essayer d'y ramener d'autres probl�mes de l'algorithmique des op�rateurs lin�aires. Dans cette double perspective, nous nous int�ressons ici aux calculs en bonne complexit� de multiples communs d'op�rateurs � coefficients polynomiaux g�n�raux. Il appara�t tout d'abord que le calcul de p.p.c.m. it�r�s est une mauvaise approche. Nous d�veloppons ensuite une premi�re reformulation lin�aire du probl�me donnant une borne pr�cise sur le degr� des coefficients du p.p.c.m. en fonction des degr�s des entr�es. Cette borne permet l'analyse de plusieurs algorithmes, existants ou nouveaux, pour le calcul du p.p.c.m. Une meilleure complexit� est obtenue en rel�chant la contrainte de minimalit� du p.p.c.m. : une nouvelle reformulation lin�aire montre qu'il existe des multiples communs de taille bien moindre que celle du p.p.c.m. En en calculant deux en bonne complexit�, puis en en prenant un p.g.c.d., on obtient un bon algorithme pour le calcul du p.p.c.m. (Travail en cours avec A. Bostan, Z. Li et B. Salvy.)