Complexité de la multiplication : Joris van der Hoeven récompensé

La multiplication a beau être une opération élémentaire, elle pose toujours des questions aux spécialistes. Une en particulier : quelle est sa complexité, c’est-à-dire la quantité de ressource (en termes d’étapes ou de temps de calcul) nécessaire pour mener l’opération jusqu’au bout ? Si les ordinateurs utilisaient la méthode que nous avons apprise à l’école pour effectuer des multiplications, il leur faudrait environ 30 ans pour multiplier deux nombres comprenant chacun un milliard de chiffres. Or, cela leur prend seulement quelques secondes car ils utilisent une méthode -un algorithme- bien plus efficace. Mais serait-il possible de faire encore mieux ?

Joris van der Hoeven, directeur de recherche au CNRS affilié au Laboratoire d’informatique de l’Ecole polytechnique (LIX*) s’est plongé dans ce problème en compagnie du mathématicien David Harvey de l'université de Nouvelle-Galles du Sud. En 2019, ils ont annoncé un résultat majeur publié depuis dans la revue Annals of Mathematics : l’algorithme de multiplication le plus efficace à ce jour. Ce résultat vaut la médaille N.G. de Bruijn à Joris van der Hoeven. « Le prix est destiné aux chercheurs de nationalité néerlandaise ou travaillant aux Pays-Bas, mais je tiens évidemment à le partager avec David Harvey » précise le chercheur du LIX.

La complexité, une notion centrale

Estimer la complexité des algorithmes est un problème important pour les spécialistes à l’interface entre les mathématiques et l’informatique, non seulement pour des perspectives pratiques -calculer plus vite- mais aussi théorique : cela permet d’éclairer la nature mathématique du problème. De plus, la multiplication est une brique de base de très nombreux autres algorithmes.

Si on multiplie deux nombres de taille n avec l’algorithme appris à l’école, la complexité est proportionnelle à n². Mais depuis les années 1960, des algorithmes de plus en plus performants ont été découverts. Leur principe général consiste à essayer de remplacer le plus possible les multiplications élémentaires par des additions, moins complexes. Ainsi, l’algorithme de Schönhage et Strassen, proposé en 1971, avait une complexité de l’ordre de n x log n x log (log n), ou log désigne la fonction logarithme.

« Mais Schönhage et Strassen conjecturaient que la complexité de la multiplication pouvait être réduite à n x log n, sans toutefois proposer de manière d’y arriver » explique Joris van der Hoeven, qui a commencé à plancher sur ce problème avec David Harvey dès 2014. Ils ont repris et pousser encore plus loin l’utilisation d’un outil déjà utilisé par les méthodes précédentes : la transformée de Fourier rapide (FFT). Elle permet, grosso-modo de ramener la multiplication sur des nombres de taille n à la multiplication sur des nombres de taille log n. « Nous avons plusieurs fois réussi à diminuer la complexité, sans atteindre la borne n x log n. Nous y sommes finalement parvenus, à notre grande surprise » se rappelle le chercheur du LIX.

Cet algorithme est aujourd’hui le plus rapide connu pour multiplier, du moins en théorie. L’implémentation pratique est une autre histoire, car elle dépend intimement de l’architecture des processeurs d’ordinateurs, et les puces d’aujourd’hui optimisent beaucoup plus les opérations de multiplications que les additions. Enfin, même en théorie, l’existence d’un algorithme à la complexité encore plus petite reste ouverte. « Personnellement, je ne le pense pas » souligne Joris van der Hoeven, mais nous n’en avons pas encore la preuve ».

*LIX : une unité mixte de recherche CNRS, École polytechnique - Institut Polytechnique de Paris