Lorsque l'on se propose d'implanter des opérations arithmétiques de base pour différents types mathématiques (entiers, polynômes, matrices, opérateurs différentiels, séries, etc.), la multiplication joue un rôle central. Premièrement, beaucoup d'autres opérations (division, pgcd, etc.) se ramènent à la multiplication. Deuxièmement, la complexité de la multiplication peut être utilisée comme étalon pour mesurer les complexités d'autres opérations. Enfin, l'étude approfondie de la complexité de multiplication dans une nouvelle algèbre nous renseigne souvent sur des représentations alternatives pour les éléments de et des techniques efficaces pour calculer avec.

Dans les deux exposés, nous survolons des algorithmes efficaces de multiplication pour différentes algèbres et sous l'angle de la complexité asymptotique. Dans le premier exposé, nous commençons avec la multiplication des entiers et des polynômes, tout en survolant différentes techniques pour effectuer des transformations de Fourier discrètes. Dans le deuxième exposé, nous nous tournons vers d'autres algèbres : des matrices de polnômes, des séries, des opérateurs différentiels, des tours algébriques, et des polynômes creux en plusieurs variables.

Occasion: JNCF 2022, Luminy, 29 février et 1 mars, 2022

Documents: slideshow-1, slideshow-2, TeXmacs source