Factorisation de polynômes à deux variables convexe-denses

par Jérémy Berthomieu (LIX, École polytechnique)

jeudi 24 févr. 2011, 10:30 → 11:30 Europe/Paris

XR.203 (Bâtiment XLIM)

Nous présentons un nouvel algorithme pour réduire le problème de la factorisation des polynômes creux à deux variables au cas des polynômes denses. Cette réduction consiste simplement en le calcul d'une transformation monomiale inversible qui rend un polynôme dont la taille dense est du même ordre de grandeur que la taille du polygone de Newton du polynôme donné en entrée. En particulier, si la complexité d'un algorithme de factorisation de polynôme à deux variables s'exprime en le produit des degrés partiels, notre résultat permet de dire que cette même complexité est en fait en la taille du polygone de Newton du polynôme considéré.