November 26, 2018
Bruno Grenet (LIRMM - Université de Montpellier)Le calcul formel s’intéresse à l’algorithmique des objets mathématiques exacts, en particulier des polynômes et des matrices. Depuis les années 1960, de nombreux algorithmes ont été proposés pour atteindre des complexités temporelles quasi-optimales (quasi-linéaires en la taille des entrées et des sorties) pour manipuler des polynômes. Dans ce travail, nous nous intéressons à obtenir des versions efficaces en mémoire de ces algorithmes, c’est-à-dire des algorithmes qui n’utilisent qu’une mémoire constante en plus des registres d’entrée et de sortie.
Nous développons pour ce faire des méthodes génériques de réduction qui permettent de transformer n’importe quel algorithme pour une tâche donnée en un algorithme de même complexité temporelle asymptotique, et de complexité spatiale améliorée, dans la veine des réductions pour la complexité à grain fin. Dans l’exposé, nous nous concentrerons sur les problèmes basiques autour de la multiplication de polynômes et évoquerons brièvement les extensions à d’autres problèmes comme la division euclidienne ou l’interpolation.
Travail en cours, en commun avec Pascal Giorgi et Daniel S. Roche.