Préparation Agrégation Externe Rennes 1 Matthieu Romagny, 25 septembre 2018

Transformation de Fourier discrète

Le paragraphe 13.6 du programme de l’Agrégation s’intitule « Transformée de Fourier » et contient

les thèmes : Transformée de Fourier discrète sur un groupe abélien fini. Transformée de Fourier
rapide. Nous allons motiver l’utilisation de la transformée de Fourier discrète par le problème de la
multiplication de (grands) polynômes, puis décrire l’algorithme FFT qui est la raison de l’efficacité
de la méthode, puis enfin revenir sur la dénomination « Transformée de Fourier ».
Une référence possible pour les parties 1 et 2 est le livre :
A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, É. Schost,
Algorithmes Efficaces en Calcul Formel,
disponible à l’adresse [Link]

1 Multiplication de polynômes sur machine

Soit K un corps. Dans les applications, on est intéressé par les corps K = Q, R, C, Fq ( 1 ). En
machine, on utilise en général l’une des deux représentations pour les polynômes :
- dense : P = ni=0 ai xi , an 6= 0 est représenté par [a0 , . . . , an ],
P

- creuse : P = di=0 ai xei , e0 < · · · < ed , ai 6= 0, est représenté par [e0 , a0 , . . . , ed , ad ].

P

Dans la suite, travaillons avec la représentation dense. Nous voulons additionner et multiplier les
polynômes de manière efficace. Le coût est mesuré par le nombre d’opérations à effectuer dans le
corps de coefficients K. Si on veut additionner deux polynômes P et Q de degré < n, la méthode
naïve coefficientP par coefficient requiert n additions. Si on veut les multiplier, le calcul de chaque
coefficient ck = i+j ai bj nécessite n multiplications puis n additions, soit un coût total de 2n2 (le
calcul précis tenant compte des effets de bord avec les indices fournit la même asymptotique en 2n2 ).
C’est donc quadratique. L’enjeu est de réduire ce coût.
La transformation de Fourier discrète permet de faire bien mieux. L’idée est en quelque sorte
de passer à une troisième représentation des polynômes, précisément la représentation par leurs
valeurs sur un n-uplet de points. En effet, l’interpolation de Lagrange nous dit qu’un polynôme P
de degré < n est déterminé de manière unique par les valeurs P (a1 ), . . . , P (an ) si les ai ∈ K sont
tous distincts. Lorsque le corps K contient les racines n-èmes de l’unité 1, ζ, . . . , ζ n−1 , le choix des
valeurs ai = ζ i permet de mettre en place un algorithme récursif qui mène à une grande efficacité. Le
lien avec la transformation de Fourier sur le groupe G = Z/nZ s’explique par le fait que le groupe
Gb = {1, ζ, . . . , ζ n−1 } est le groupe dual de G, et nous y reviendrons.

1.1 Remarque. Pour être plus précis, l’expression « le corps K contient les racines n-èmes de
l’unité » signifie que le cardinal de l’ensemble µn (K) := {x ∈ K, xn = 1} est égal à n. On sait que
|µn (K)| 6 n car le polynôme X n − 1 ∈ K[X] a au plus n racines. On ne peut avoir |µn (K)| = n
que si n est premier avec la caractéristique p > 0 de K (condition vide si p = 0). En effet, si p > 0
et n = pm est multiple de p, l’égalité xn = 1 implique (xm − 1)p = 0 donc xm = 1 si bien que
µn (K) ⊂ µm (K) dont le cardinal est au plus m.
1. Les corps Q et Fq sont plus propices à une implémentation machine que les corps R et C dont les éléments sont
intrinsèquement complexes.

1
2 Transformation de Fourier discrète et algorithme FFT
On fixe un corps K contenant n racines n-èmes de l’unité. On rappelle que, comme tout sous-
groupe fini du groupe multiplicatif d’un corps (commutatif), le groupe µn (K) est cyclique. On note
µ∗n (K) l’ensemble des racines primitives n-èmes de l’unité, qui sont les générateurs de µn (K).
2.1 Remarque. Sur un corps qui ne contient pas assez de racines de l’unité, on peut tout de même
définir une transformation de Fourier discrète et un algorithme FFT en se plaçant sur un anneau
plus grand A = K[X]/(X n + 1) obtenu en ajoutant des racines de l’unité. Cet anneau n’est pas
nécessairement un corps, ni même intègre, et c’est pourquoi il est utile de présenter l’algorithme FFT
sur un anneau effectif général. Dans ce texte, nous restons avec un corps K pour simplifier.
Fixons une racine primitive n-ème de l’unité ω. Pour tout polynôme K ∈ K[X] qui est multiple
de X n − 1, les valeurs F (ω i ) sont nulles. On peut donc définir l’application transformation de Fourier
discrète :
DFTω : K[X]/(X n − 1) → K n , F 7→ (F (1), F (ω), . . . , F (ω n−1 )).
C’est un morphisme de K-algèbres, lorsqu’on voit le but K n comme l’algèbre produit où la multipli-
cation se fait composante par composante. Son calcul rapide est effectué par un algorithme de type
« diviser pour régner ». Pour appliquer cette idée, supposons que n est pair, n = 2k. Alors, ω k = −1
puisque (ω k − 1)(ω k + 1) = ω n − 1 = 0 et le premier facteur est différent de 0. On peut écrire deux
divisions euclidiennes :
F = (X k − 1)Q0 + R0 , F = (X k + 1)Q1 + R1 avec deg R0 , deg R1 < k.
Ces écritures vont nous permettre le calcul de F sur les puissances paires et impaires de ω. En effet,
si ` est pair, ω k` = 1 donc F (ω ` ) = R0 (ω ` ),
si ` est impair, ω k` = −1 et F (ω ` ) = R1 (ω ` ).
Outre l’application récursive, le point crucial qui est la source de l’efficacité de l’algorithme FFT et
qui conduit au choix de racines primitives de l’unité est que le calcul de R0 et R1 est très simple. On
le voit dans l’étape 2 de l’algorithme que nous présentons maintenant.

2
 3n
2.2 Théorème. Supposons que n est une puissance de 2. L’algorithme FFT requiert au plus 2
log n
opérations dans K.

Preuve : Les puissances de ω sont connues donc ne coûtent rien. Le coût de l’appel en degré n
est majoré par : n/2 additions (calcul de R0 ), plus n/2 soustractions et n/2 multiplications (calcul
de R̄1 ), plus deux appels récursifs en degré n/2. La complexité C(n) satisfait donc à la récurrence :
3n
C(n) 6 + 2C(n/2).
2
En posant D(m) = C(2m ) on obtient D(m) 6 3 · 2m−1 + 2D(m − 1) puis par récurrence :

D(m) 6 3i2m−1 + 2i D(m − i) pour tout i 6 m.

Pour i = m on obtient D(m) 6 3k2m−1 puisque D(0) = 0. En repassant à n = 2m i.e. m = log2 n on

obtient C(n) 6 3n
2
log n comme annoncé. 

Nous démontrons maintenant que le morphisme DFTω : K[X]/(X n − 1) → K n est un iso-

morphisme et que dans des bases convenables, son inverse, l’interpolation, n’est rien d’autre que
l’application DFTω−1 à un facteur n1 près. On rappelle que n est inversible dans K, cf remarque 1.1.

2.2.1 Proposition. L’application DFTω : K[X]/(X n − 1) → K n est un isomorphisme. Dans la base

{1, X, . . . , X n−1 } à la source et la base canonique au but, sa matrice est la matrice de Vandermonde :
 
1 1 ... 1
 1 ω . . . ω n−1 
Vω =  .. .
 
..
 . . 
2
1 ω n−1 . . . ω (n−1)

La matrice de l’isomorphisme inverse est n1 Vω−1 .

Preuve : L’image de X i par DFTω est le uplet (1, ω i , . . . , ω i(n−1) ) qui est bien la i-ème colonne de la
matrice de Vandermonde. Il nous reste à montrer que Vω Vω−1 = nIn . Pour 0 6 i, j 6 n − 1 on calcule
le coefficient (i, j) du produit A := Vω Vω−1 :
n−1
X n−1
X
ai,j = ω ik ω −kj = ω (i−j)k .
k=0 k=0

(i−j)n
Lorsque i 6= j, on a ω i−j 6= 1 donc ai,j = ωωi−j −1−1 = 0. Lorsque i = j, ai,j = ai,i est une somme de n
termes égaux à 1, donc égal à n. Ceci termine le calcul. 

Revenons au problème du calcul du produit de deux polynômes P, Q ∈ K[X] tels que deg(P ) +
deg(Q) < n, par exemple avec les degrés tous deux < n/2. Alors les polynômes P, Q et P Q sont
tous trois égaux à leur reste dans la division euclidienne par X n − 1, i.e. on peut les identifier à leur
image dans K[X]/(X n − 1). Pour les multiplier, on appliquera la transformation de Fourier DFTω
dont le calcul par l’algorithme FFT se fait en O(n log n) opérations, puis on calcule les produits
des valeurs P (ω i )Q(ω i ) ce qui coûte n opérations, puis on interpole pour revenir en représentation
dense, ce qui se fait par un algorithme FFT associé à DFTω−1 pour un coût en O(n log n). Au total
la multiplication peut être effectuée en O(n log n) opérations.

3
3 Vous avez dit transformation de Fourier ? !
Mais pourquoi ça s’appelle une transformée de Fourier ? Nous allons voir.

3.1 Transformation de Fourier sur R. Soit f une fonction intégrable sur R, à valeurs complexes.
Sa transformée de Fourier est la fonction fb définie par :
Z
1
f (χ) = √
b e−iχx f (x)dx.
2π R

L’opération F : f 7→ fb envoie la convolution sur le produit point par point :

1 ∗ f2 = f1 f2
f\ b b
R
où h = f1 ∗ f2 est définie par h(x) = R f1 (x − t)f2 (t)dt. Soulignons que ce produit de convolution
doit son existence à, ou est un reflet de, la loi de groupe de R.

3.2 Remarques. Il y a quelques petits problèmes :

(1) Si on veut que le produit de convolution possède un élément neutre, le bon cadre est celui des
distributions et le neutre est la masse de Dirac δ0 . De plus, pour a, b ∈ R on a la formule δa ∗ δb = δa+b
pour la convolution de deux masses de Dirac. Ceci montre bien l’interaction avec la loi de groupe.
(2) Si f1 ∈ L1 et f2 ∈ L1 , alors f1 ∗ f2 ∈ L1 . Mais un tel résultat de stabilité n’a pas lieu dans Lp
pour p 6= 1. (En général, l’inégalité de Young dit que si 1 6 p, q, r 6 ∞ et p1 + 1q = 1 + 1r , alors f ∈ Lp ,
g ∈ Lq =⇒ f ∗ g ∈ Lr et même kf ∗ gkr 6 kf kp · kgkq . Ainsi Lp n’est stable par convolution que pour
p = 1.) Or, on est aussi intéressé par la transformée de Fourier dans d’autres espaces, comme L2 .
Dans le cas où G est un groupe fini, tous ces problèmes disparaîtront.

3.3 Transformation de Fourier sur des groupes localement compacts. Le domaine d’inté-
gration G = R est un groupe abélien, muni d’une topologie pour laquelle il est localement compact
(ce qui signifie qu’il est séparé et que chaque point de G possède un voisinage compact – dans notre
exemple, simplement une petite boule fermée). D’autres exemples de tels groupes sont G = S 1 = U
le cercle unité ou groupe des complexes de module 1, ou G = Z, ou G = Z/nZ. (Les produits finis de
tels groupes sont d’autres possibilités, par exemple tous les groupes abéliens de type fini.) Or, il existe
une théorie de la transformation de Fourier sur de tels groupes. Parmi les ingrédients nécessaires pour
l’expliquer, figurent deux notions importantes :

3.4 Définitions. (1) Un caractère de G est un morphisme de groupes χ : G → U.

(2) Une mesure de Haar sur G est une mesure borélienne positive invariante sur G, i.e. une mesure
µ : B(G) → R>0 définie sur la tribu des boréliens de G (tribu engendrée par les ouverts), et qui est
invariante i.e. µ(g + A) = µ(A) pour tous A ∈ B(G) et g ∈ G. (Sur des groupes non abéliens, on
peut distinguer invariance à droite et invariance à gauche.)

3.5 Théorème (Alfréd Haar, 1933). Tout groupe abélien topologique localement compact G pos-
sède une mesure de Haar µ et celle-ci est unique à multiplication par un scalaire > 0 près.

4
 Lorsque G est compact, on a µ(G) < +∞ et on peut normaliser de sorte que µ(G) = 1, ce qui la
rend véritablement unique. La mesure de Haar de G = R est la mesure de Lebesgue λ, et la mesure
1
de Haar de U est 2π λ. Pour G = Z/nZ, la mesure de Haar est la mesure de comptage :

|A|
µ(A) = |G| pour toute partie A ⊂ G
1
R P
G
f dµ = |G| g∈G f (g) pour toute fonction f : G → C.

Notons G b = Hom(G, U) l’ensemble des caractères de G. Muni du produit point par point, c’est un
groupe et muni de la norme de la convergence uniforme sur tout compact, il est localement compact.
On définit la transformée de Fourier d’une fonction f : G → C comme étant la fonction fb : Gb→C
définie, pour tout caractère χ : G → U, par :
Z
f (χ) =
b χ(g)f (g)dµ.
G

Notons F (G) l’ensemble des fonctions à valeurs complexes sur G qui sont intégrables (avec les nuances
imposées par 3.2(2)). Ainsi, la transformée de Fourier met en correspondance deux algèbres :

F /
(F (G), ∗) o b ·) .
(F (G),
F −1

3.6 Transformation de Fourier sur U. Rappelons que l’exponentielle R → U, x 7→ e2iπx est un

morphisme de groupes de noyau Z qui identifie U au quotient R/Z. De même, pour tout n ∈ Z,
l’application R → U, x 7→ e2iπnx est un morphisme de groupes dont le noyau contient Z. Il induit
donc un caractère χn : U ' R/Z → U. On montre que l’application Z → U, b n 7→ χn est un
isomorphisme de groupes (ici discrets). La transformée de Fourier d’une fonction f : U → C est la
b ' Z → C qui associe à n son n-ème coefficient de Fourier cn . La formule d’inversion
fonction fb : U
de Fourier dit que
X
f (x) = cn e2iπnx .
n∈Z

La théorie de Fourier sur U est simplement la théorie des séries de Fourier des fonctions périodiques.

3.7 Transformation de Fourier sur Z/nZ. P Explicitons tout ceci pour G = Z/nZ. L’espace F (G)
est de dimension finie et la formule f = g∈G f (g)δg montre que les indicatrices δg , g ∈ G, forment
une base. La propriété δa ∗δb = δa+b (cf 3.2(1)) permet de voir qu’on a un isomorphisme de C-algèbres :

C[X]
∼
(F (Z/nZ), ∗) −→ , δa 7→ X a . (1)
(X n − 1)

∼
b −→
On a un isomorphisme G µn (C), χ 7→ χ(1) entre le groupe dual et le groupe µn := µn (C) des
racines n-èmes complexes de l’unité. (L’isomorphisme inverse associe à une racine de l’unité ω le
caractère défini par χ(i) = ω i .) Chaque choix de racine primitive de l’unité ω ∈ µ∗n (C) détermine un
isomorphisme Z/nZ → µn := µn (C) qui envoie i sur ω i . Il en résulte un isomorphisme de C-algèbres :

(F (µn ), ·) = Cµn −→
∼
Cn (2)

5
où le but est l’algèbre produit, dans laquelle le produit se fait composante par composante. Une fois
les algèbres de fonctions F (Z/nZ) et F (µn ) décrits concrètement à l’aide de (1) et (2), la transformée
de Fourier F : (F (G), ∗) → (F (G),
b ·) est donc un isomorphisme

C[X] ∼
−→ Cn
(X n − 1)

qui n’est autre que l’isomorphisme DFTω donné par l’évaluation des polynômes en les n racines de
l’unité i.e. F 7→ (F (1), F (ω), . . . , F (ω n−1 )). Ce qui explique ce que nous voulions expliquer.