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.)