Exercice 18 - Transformée discrète de Fourier

Nous allons étudier la transformée discrète de Fourier et la façon dont on peut la calculer efficacement. Etant donné un vecteur $a = (a_0, \ldots, a_{n-1})$, la transformée discrète de Fourier de $a$ est un vecteur $b = (b_0, \ldots, b_{n-1})$, noté $b = TF(a)$ dont le $p$-ème élément est

$$b_p = \sum_{k=0}^{n-1} a_k (e^{\frac{p}{n}2 \pi i})^k$$

1. Commençons par étudier les racines complexes de $1$. Vous vous doutez probablement $1$ a deux racines carrées $-1$ et $1$. Vérifiez que $1$, $$\frac{-1}{2} + \frac{\sqrt{3}}{2}i$$ et $$\frac{-1}{2} - \frac{\sqrt{3}}{2}i$$ sont $3$ racines cubiques de $1$.
2. Vérifiez que $1$, $1 + i$, $-1$ et $1 - i$ sont $4$ racines quatrièmes de $1$.
3. Vérifiez que $$W_n = \{e^{\frac{1}{n}2\pi i + \frac{k}{n}2i\pi} \vert k \in \{0, \ldots, n - 1\}\}$$ est l'ensemble des racines $n$-èmes de $1$.
4. Posons $$\omega_n = e^{\frac{1}{n}2\pi i}$$, véfifiez que $$W_n = \{\omega_n^k \vert k \in \{0, \ldots, n-1\}\}$$.
5. Prouvez que pour tous $n$ et $k$, $\omega_{n}^{k + n} = \omega_{n}^{k}$.

On considère l'algorithme

1. Soit $$P(x) = a_0 + \sum_{i = 1}^{n-1}a_ix_i$$ un polynome de degré $n-1$. Que vaut l'algorithme $A(P, x, n)$ ?
2. Quelle est la complexité de $A$ ?
3. La méthode de Horner est basée sur la relation suivante $$P(x) = a_0 + x (a_1 + x(a_2 + x(\ldots)))$$. Ecrivez l'algorithme récursif $horner$ qui calcule $P(x)$ en utilisant cette relation.
4. Quelle est la complexité de $horner$ ?
5. Soit $$P(x) = a_0 + \sum_{i = 1}^{n-1}a_ix_i$$ un polynôme de degré $n-1$ et $b = TF(a)$. Montrez que $b_p = P(w_n^p)$.
6. Comment calculer $TF(a)$ en utilisant le sous-programme $horner$ ? Ecrivez le sous-programme $TF$.
7. On note $TF^{-1}$ la transformée inverse de Fourier, nous admettrons que si $a = TF^{-1}(b)$, alors
   
   $$a_q = \frac{1}{n} \sum_{k=0}^{n-1} b_k \omega_n^{-kq}$$
   
   
   Ecrivez le sous-programme $TF^{-1}$.
8. Quelle sont les complexités de $TF$ et de $TF^{-1}$ ?
9. Prouvez que pour tous $n$ et $k$, $\omega_{2n}^{2k} = \omega_{n}^{k}$.
10. Supposons que $n$ est pair, donc qu'il existe $m$ tel que $n = 2m$. Soit $a^{[0]} = (a_0, a_2, \ldots, a_{2m})$, $a^{[1]} = (a_1, a_3, \ldots, a_{2m+1})$, $b^{[0]} = TF(a^{[0]})$ et $b^{[1]} = TF(a^{[1]})$. Soit $q \in \{0, \ldots, m-1\}$, montrez que
    
    $$b_q = b^{[0]}_q + \omega_n^qb^{[1]}_q$$
    
    
    puis que
    
    $$b_{q+m} = b^{[0]}_q + \omega_n^{q + m}b^{[1]}_q$$
    
    

11. Ecrire le sous-programme $FFT$ qui calcule la transformée discrète de Fourier d'un vecteur de taille $n = 2^k$ en utilisant la relation de récurrence ci-dessus.
12. Quelle est la complexité de $FFT$ ?
13. Supposons que $n$ est pair, donc qu'il existe $m$ tel que $n = 2m$. Soit $b^{[0]} = (b_0, b_2, \ldots, b_{2m})$, $b^{[1]} = (b_1, b_3, \ldots, b_{2m+1})$, $y^{[0]} = TF^{-1}(b^{[0]})$ et $y^{[1]} = TF^{-1}(b^{[1]})$. Soit $p \in \{0, \ldots, m-1\}$ et $y = TF^{-1}(b)$. Montrez que
    
    $$y_p = \frac{1}{2}(y^{[0]}_p + \omega_n^{-p}y^{[1]}_p )$$
    
    
    puis que
    
    $$y_{p+m} = \frac{1}{2}(y^{[0]}_p + \omega_n^{-(p + m)}y^{[1]}_p )$$
    
    

14. Ecrire le sous-programme $FFT^{-1}$ qui calcule la transformée inverse de Fourier d'un vecteur de taille $n = 2^k$ en utilisant la relation de récurrence ci-dessus.
15. Quelle est la complexité de $FFT^{-1}$ ?
16. Ecrivez les fonctions du fichier fourier.c correspondant au fichier fourier.h ci-dessous.

#ifndef FOURIER_H
#define FOURIER_H

#include"linkedList.h"
#include"complexe.h"

/*
  Retourne la transformee discrete de Fourier du vecteur l. 
  Algorithme iteratif en O(n^2).
 */
linkedList* transformeeFourierIt(linkedList* l);

/*
  Retourne la transformee discrete de Fourier inverse 
  du vecteur l. Algorithme iteratif en O(n^2).
 */
linkedList* transformeeInverseFourierIt(linkedList* l);

/*
  Retourne la transformee discrete de Fourier du vecteur l, de taille 
  n = 2^m. Algorithme recursif en O(n log n).
 */
linkedList* FFT(linkedList* l);

/*
  Retourne la transformee discrete de Fourier inverse 
  du vecteur l de taille n = 2^m. Algorithme recursif en
  O(n log n).
 */
linkedList* inverseFFT(linkedList* l);

#endif

fourier.h

Vous utiliserez les fonctions auxiliaires suivantes :

1. linkedList* uniteRacinesComplexe(complexe c, unsigned long n), retourne les n racines n-ème de $1$.
2. complexe horner(link* p, complexe x), retourne l'image de x par le polynôme p.