human
Veuillez expliquer ce qu'est la "transformée de Fourier rapide"
gpt
Une transformée de Fourier rapide (FFT) est un algorithme qui calcule la transformée de Fourier discrète (DFT) d'une séquence, ou son inverse (IDFT). L'analyse de Fourier convertit un signal de son domaine d'origine (souvent temporel ou spatial) en une représentation dans le domaine fréquentiel et vice versa. La DFT est obtenue en décomposant une séquence de valeurs en composantes de fréquences différentes. Cette opération est utile dans de nombreux domaines, mais la calculer directement à partir de la définition est souvent trop lent pour être pratique. Une FFT calcule rapidement de telles transformations en factorisant la matrice DFT en un produit de facteurs clairsemés (principalement nuls). En conséquence, il parvient à réduire la complexité du calcul de la DFT à partir de



O

(

N

2


)



{\textstyle O\left(N^{2}\right)}

, qui se pose si l'on applique simplement la définition de DFT, à



O
(
N
Journal
⁡
N
)


{\textstyle O(N\log N)}

, où



N


{\displaystyle N}

 est la taille des données. La différence de vitesse peut être énorme, en particulier pour les longs ensembles de données où N peut se chiffrer en milliers ou en millions. En présence d'une erreur d'arrondi, de nombreux algorithmes FFT sont beaucoup plus précis que l'évaluation directe ou indirecte de la définition DFT. Il existe de nombreux algorithmes FFT différents basés sur un large éventail de théories publiées, de la simple arithmétique des nombres complexes à la théorie des groupes et à la théorie des nombres.
Les transformées de Fourier rapides sont largement utilisées pour des applications en ingénierie, musique, sciences et mathématiques. Les idées de base ont été popularisées en 1965, mais certains algorithmes avaient été dérivés dès 1805. En 1994, Gilbert Strang a décrit la FFT comme "l'algorithme numérique le plus important de notre vie", et il a été inclus dans le Top 10 des algorithmes du 20e siècle. par le magazine IEEE Computing in Science & Engineering.
Les algorithmes FFT les plus connus dépendent de la factorisation de N, mais il existe des FFT de complexité O(N log N) pour tout N, même pour N premier. De nombreux algorithmes FFT dépendent uniquement du fait que




e

−
2
π
je

/

N




{\textstyle e^{-2\pi i/N}}

 est une N-ième racine primitive de l'unité, et peut donc être appliquée à des transformées analogues sur n'importe quel champ fini, telles que les transformées de la théorie des nombres. Étant donné que la DFT inverse est la même que la DFT, mais avec le signe opposé dans l'exposant et un facteur 1/N, tout algorithme FFT peut facilement être adapté pour cela.