ALGORITHME DE TRANSFORMÉE DE FOURIER RAPIDE (J. W. Cooley et J. W. Tukey)

La publication en 1965, dans le journal Mathematics of Computation de la Société américaine de mathématiques (AMS), de l’« Algorithme de transformée de Fourier rapide » par les mathématiciens américains James William Cooley (1926-2016) et John Wilder Tuckey (1915-2000) révolutionne l’automatisation des calculs physico-mathématiques liés à l’étude de systèmes dont l’évolution est prédite par des équations différentielles. La transformation de Fourier est un outil essentiel de l’analyse mathématique qui associe à une fonction dont la variable est le temps (ou la position spatiale) une fonction dépendant d’une fréquence (ou d’une quantité dite conjuguée de la position). Elle permet de résoudre de façon élégante et efficace des équations différentielles ou aux dérivées partielles. La transformée de Fourier discrète est une variante discontinue de cette méthode qui permet d’obtenir une représentation spectrale discrète d’un signal numérique échantillonné en un nombre fini (n) de points.

Le principe de la transformée de Fourier discrète rapide (FFT, pour Fast Fourier Transform) remonte à des travaux du mathématicien allemand Carl Friedrich Gauss en 1805. L’astuce consiste à décomposer de façon récursive le problème de taille n en deux problèmes de taille plus petite m et p (par exemple avec m=p=n/2). L’efficacité de cet algorithme s’exprime par la façon dont le nombre d’opérations élémentaires nécessaires croît avec le nombre d’échantillons : cette « complexité » varie comme n·logn, à comparer à n² pour une transformée de Fourier discrète normale. Ce gain permet de réaliser la transformation dans des cas où un traitement classique serait inenvisageable. Il existe de nombreuses variantes de la FTT. La méthode a ensuite été généralisée pour être appliquée à différentes techniques de compression numérique indispensables, par exemple au codage d’images transmissibles informatiquement.

— Bernard PIRE