Transformation de Fourier rapide

La transformation de Fourier rapide (sigle anglais : FFT ou fast Fourier transform) est un algorithme de calcul de la transformation de Fourier discrète (TFD). Sa complexité varie en O(n log n) avec le nombre n de points, alors que la complexité de l’algorithme « naïf » s'exprime en O(n). Ainsi, pour n = , le temps de calcul de l'algorithme rapide peut être 100 fois plus court que le calcul utilisant la formule de définition de la TFD. C'est en 1965 que James Cooley et John Tukey publient l’article qui « lance » définitivement l'adoption massive de cette méthode en traitement du signal et dans les télécommunications. On a découvert par la suite que l'algorithme avait déjà été imaginé par Carl Friedrich Gauss en 1805, et adapté à plusieurs reprises (notamment par Lanczos en 1942) sous des formes différentes. L'algorithme a aussi été découvert indépendamment par le chanoine Lemaître. Cet algorithme est couramment utilisé en traitement numérique du signal pour transformer des données discrètes du domaine temporel dans le domaine fréquentiel, en particulier dans les oscilloscopes numériques (les analyseurs de spectre utilisant plutôt des filtres analogiques, plus précis). Son efficacité permet de réaliser des filtrages en modifiant le spectre et en utilisant la transformation inverse (filtre à réponse impulsionnelle finie). Il est également à la base des algorithmes de multiplication rapide (Schönhage et Strassen, 1971), et des techniques de ayant mené au format d'image JPEG (1991). Le développement d'algorithmes rapides pour la FFT remonte au travail non publié de Carl Friedrich Gauss en 1805, alors qu'il en avait besoin pour interpoler l'orbite des astéroïdes Pallas et Junon à partir d'observations d'échantillons. Sa méthode était très similaire à celle publiée en 1965 par James Cooley et John Tukey, à qui l'on attribue généralement l'invention de l'algorithme générique moderne de la FFT. Bien que les travaux de Gauss soient antérieurs aux résultats de Joseph Fourier en 1822, il n'a pas analysé le temps de calcul et a finalement utilisé d'autres méthodes pour atteindre son objectif.