Transformée de Fourier discrète

algebra

On dispose en mathématiques de quatre opérations dites élémentaires : l’addition, la soustraction, la division et donc la multiplication. On sait tous multiplier deux entiers en base $10$ : il suffit de faire la multiplication de chaque chiffre du multiplicateur par chaque chiffre du multiplicande, puis d’additionner le tout. Pour deux nombres de taille $n$ , cela donne un algorithme de complexité $O (n^{2})$ . Mais dès que l’on veut multiplier de très grands chiffres (en informatique par exemple), cet algorithme montre très vite ses limites. Nous allons étudier ici le cas des polynômes en donnant un algorithme de multiplication utilisant la transformée de Fourier rapide.

Transformée de Fourier discrète sur $C$

Définitions

L’idée va être d’identifier les polynômes de degré inférieur à $n - 1$ de la forme $\sum_{k = 0}^{n - 1} a_{k} x^{k}$ au vecteur de $C^{n}$ $(a_{0}, \dots, a_{n - 1})$ . On fixe, pour toute la suite, $ω$ une racine primitive $n$ -ième de l’unité.

Définition 1. On appelle transformée de Fourier discrète l’application $DFT_{ω} : C^{n} (f_{0}, \dots, f_{n - 1}) \to \mapsto C^{n} (\sum_{k = 0}^{n - 1} f_{k}, \sum_{k = 0}^{n - 1} f_{k} ω^{k}, \dots, \sum_{k = 0}^{n - 1} f_{k} ω^{(n - 1) k})$

Remarque 2. Si $F$ est le polynôme associé au vecteur $f = (f_{0}, \dots, f_{n - 1})$ , on a $DFT_{ω} (f) = (F (1), \dots, F (ω^{n - 1}))$ fait que nous utiliserons plusieurs fois dans la suite.

Dans un premier temps, on peut écrire l’algorithme de calcul suivant.

Algorithme 3.

# Exponentiation rapide. Calcul x^n.
def power(x, n):
    if n == 0:
        return 1
    if n == 1:
        return x
    if n % 2 == 0:
        return power(x*x, n//2)
    return x * power(x*x, (n-1)//2)

# Algorithme naïf pour calculer la transformée de Fourier rapide de f.
def naive_dft(f, omega):
    n = len(f)
    return [sum(f[k] * power(omega, i*k) for k in range(n)) for i in range(n)]

Définition 4. Le produit de convolution de deux vecteurs $f = (f_{0}, \dots, f_{n - 1})$ et $g = (g_{0}, \dots, g_{n - 1})$ de $C^{n}$ est le vecteur de $C^{n}$ noté $f *_{n} g$ défini par $f *_{n} g = i + j \equiv k mod n \sum f_{i} g_{j}_{k \in [[0, n - 1]]}$

Exemple 5. $DFT_{- 1} (1, 3) = (4, - 2)$ et $(1, 3) *_{2} (1, 3) = (1 + 9, 3 + 3) = (10, 6)$ .

Propriétés

Proposition 6. Soient $f = (f_{0}, \dots, f_{n - 1})$ , $g = (g_{0}, \dots, g_{n - 1})$ deux vecteurs de $C^{n}$ . On pose $h = f *_{n} g = (h_{0}, \dots, h_{n - 1})$ ainsi que $F$ , $G$ et $H$ les polynômes associés respectivement à $f$ , $g$ et $h$ . Modulo $X^{n} - 1$ , on a : $\overline{H} = \overline{FG}$

Démonstration. Écrivons : $H = k = 0 \sum n - 1 i + j \equiv k mod n \sum f_{i} g_{j} X^{k}$ Comme $H$ est au plus de degré $n - 1$ , on a $H = \overline{H}$ (par abus de notation). Maintenant avec $F = \sum_{k = 0}^{n - 1} f_{k} X^{k}$ et $G = \sum_{k = 0}^{n - 1} g_{k} X^{k}$ , on a : $FG = k = 0 \sum 2 n - 2 i + j = k \sum f_{i} g_{k - i} X^{k} = k = 0 \sum n - 1 i + j = k \sum f_{i} g_{k - i} X^{k} + k = n \sum 2 n - 2 i + j = k \sum f_{i} g_{k - i} X^{k} = k = 0 \sum n - 1 i + j = k \sum f_{i} g_{k - i} X^{k} + X^{n} k = 0 \sum n - 2 i + j = n + k \sum f_{i} g_{k - i} X^{k}$ En passant modulo $X^{n} - 1$ , $\overline{F} \overline{G} = \overline{FG} = k = 0 \sum n - 1 (i = 0 \sum k f_{i} g_{k - i}) \overline{X^{k}} + k = n \sum 2 n - 2 (i = 0 \sum k f_{i} g_{k - i}) \overline{X^{k}} = \overline{X^{n}} = \overline{1} k = 0 \sum n - 1 (i = 0 \sum k f_{i} g_{k - i}) \overline{X^{k}} + k = 0 \sum n - 2 i + j = n + k \sum f_{i} g_{k - i} \overline{X^{k}} = k = 0 \sum n - 1 i + j \equiv k mod n \sum f_{i} g_{j} \overline{X^{k}} = \overline{H}$ ◻

Théorème 7. $DFT_{ω}$ est un isomorphisme d’algèbres entre $(C^{n}, +, *_{n})$ et $(C^{n}, +, \cdot)$ dont la matrice dans la base canonique est la matrice de Vandermonde : $V_{ω} = 111 ⋮ 1 1 ω ω^{2} ⋮ ω^{n - 1} 1 ω^{2} ω^{4} ⋮ ω^{2 (n - 1)} \dots \dots \dots ⋱ \dots 1 ω^{n - 1} ω^{2 (n - 1)} ⋮ ω^{(n - 1)^{2}}$ (où $\cdot$ est le produit sur $C^{n}$ effectué composante par composante.)

Démonstration. Soient $f = (f_{0}, \dots, f_{n - 1})$ et $g = (g_{0}, \dots, g_{n - 1})$ deux vecteurs de $C^{n}$ .

$\forall λ \in C$ , $DFT_{ω} (λ f + g) = (k = 0 \sum n - 1 λ f_{k} + g_{k}, \dots, k = 0 \sum n - 1 (λ f_{k} + g_{k}) ω^{(n - 1) k}) = λ (k = 0 \sum n - 1 f_{k}, \dots, k = 0 \sum n - 1 f_{k} ω^{(n - 1) k}) + (k = 0 \sum n - 1 g_{k}, \dots, k = 0 \sum n - 1 g_{k} ω^{(n - 1) k}) = λ DFT_{ω} (f) + DFT_{ω} (g)$ $DFT_{ω}$ est bien une application linéaire.
Soit $h = f *_{n} g$ . On note $F$ , $G$ et $H$ les polynômes respectivement associés à $f$ , $g$ et $h$ .

Soit $i \in [[0, n - 1]]$ . Par la Proposition 6, on a $H = FG + Q (X^{n} - 1)$ . Ainsi, $H (ω^{i}) = (FG) (ω^{i}) + Q (ω^{i}) ((ω^{i})^{n} - 1) = (FG) (ω^{i})$ Or, le $(i + 1)$ -ième coefficient de $DFT_{ω} (f) \cdot DFT_{ω} (g)$ est $F (ω^{i}) G (ω^{i}) = (FG) (ω^{i}) = H (ω^{i})$ Donc $DFT_{ω} (f) \cdot DFT_{ω} (g) = DFT_{ω} (h)$ , et ainsi, $DFT_{ω}$ est bien un morphisme d’algèbres.
Clairement, $DFT_{ω} (f_{0}, \dots, f_{n - 1}) = V_{ω} (^{t} (f_{0}, \dots, f_{n - 1})$ donc la matrice dans la base canonique de $DFT_{ω}$ est $V_{ω}$ . Or, les $ω^{k}$ sont distincts deux-à-deux, donc $V_{ω}$ est inversible (car de déterminant non nul, en vertu de la formule de Vandermonde).

◻

Proposition 8. L’inverse de $DFT_{ω}$ est donné par $\frac{1}{n} DFT_{ω^{- 1}}$ .

Démonstration. Déjà, remarquons que si $ω$ est une racine primitive $n$ -ième de l’unité, alors $ω^{- 1}$ aussi :

$(ω^{- 1})^{n} = (ω^{n})^{- 1} = 1$ .
Et si on a $m < n$ tel que $(ω^{- 1})^{m} = (ω^{m})^{- 1} = 1$ , alors $ω^{m} = 1$ , ce qui est absurde.

Il suffit donc de montrer que $V_{ω} V_{ω^{- 1}} = n I_{n}$ . Soient $i, j \in [[1, n]]$ . En notant $c_{i, j}$ le coefficient à la $i$ -ième ligne et à la $j$ -ième colonne de $V_{ω} V_{ω^{- 1}}$ , on a : $c_{i, j} = k = 1 \sum n ω^{(i - 1) (k - 1)} ω^{(1 - j) (k - 1)} = k = 0 \sum n - 1 ω^{(i - j) k} = {n \frac{1 - ω ^{(i - j) n}}{1 - ω ^{i - j}} = ω^{n} = 1 0 si i = j sinon$ Ce qu’on voulait. ◻

Application à la multiplication de polynômes

Notre but ici va être de trouver un moyen de calculer la transformée de Fourier discrète d’un polynôme de manière efficace, puis d’en déduire un algorithme de multiplication de deux polynômes.

Proposition 9. Soit $n = 2^{k}$ , soit $ω$ une racine $n$ -ième de l’unité et soit $F \in C [x]$ de degré inférieur ou égal à $n$ . On suppose qu’il existe $F_{0}$ et $F_{1}$ tels que $F = F_{1} X^{\frac{n}{2}} + F_{0}$ et on pose $R_{0} = F_{0} + F_{1}$ et $R_{1} = F_{0} - F_{1}$ . Alors $\forall k \in [[0, \frac{n}{2}]], F (ω^{2 k}) = R_{0} (ω^{2 k}) et F (ω^{2 k + 1}) = R_{1} (ω^{2 k + 1})$

Démonstration. Écrivons $F = F_{1} X^{\frac{n}{2}} + F_{0}$ . On a donc $F - F_{0} - F_{1} = F_{1} (x^{\frac{n}{2}} - 1) ⟺ F = F_{1} (x^{\frac{n}{2}} - 1) + R_{0}$ Soit $k \in [[0, \frac{n}{2}]]$ , on évalue en $ω^{2 k}$ : $F (ω^{2 k}) = F_{1} (ω^{2 k}) (ω^{nk} - 1) + R_{0} (ω^{2 k}) = R_{0} (ω^{2 k})$ et la deuxième égalité s’obtient par un calcul similaire (en utilisant le fait que $ω^{\frac{n}{2}} = - 1$ ). ◻

Proposition 10. Si $ω$ est une racine primitive $n$ -ième de l’unité, alors $ω^{2}$ est une racine primitive $\frac{n}{2}$ -ième de l’unité.

Démonstration. Clairement, $ω^{2}$ est une racine $\frac{n}{2}$ -ième de l’unité. Maintenant, si $d ∣ \frac{n}{2}$ , alors $(ω^{2})^{d} = 1 ⟺ ω^{2 d} = 1 ⟺ 2 d = n ⟺ d = \frac{n}{2}$ ◻

On déduit de la Proposition 9 et de la Proposition 10 un algorithme récursif de calcul de $DFT_{ω}$ qui a une complexité de $O (n ln (n))$ .

Algorithme 11.

# Renvoie les indices impairs d'une liste.
def odd_indices(l):
  return [l[2*k+1] for k in range(len(l)//2)]

# Fusionne deux listes de longueur égale en alternant les termes.
def alternate_merge(l1, l2):
  return [val for pair in zip(l1, l2) for val in pair]

# Calcule et renvoie les puissances successives de la racine primitive n-ième omega.
def primitive_root_powers(omega, n):
  return [power(omega, k) for k in range(n)]

# Cette fonction renvoie la transformée de Fourier discrète de F en omega. La liste l demandée est la liste des puissances de omega.
def fft(F, m, l):
  n = m + 1
  if n == 1:
    return [0] if F == 0 else [F.list()[0]]
  (F1, F0) = F.quo_rem(X^(n/2))
  R0 = F0+F1
  R1 = F0-F1
  l2 = odd_indices(l)
  return alternate_merge(fft(R0, n/2-1, l2), fft(R1.substitute(X=l[1]*X), n/2-1, l2))

Théorème 12. Soient $F$ et $G$ deux polynômes de degré strictement inférieur à $\frac{n}{2}$ dont on note $f$ et $g$ les vecteurs de $C^{n}$ associés. Alors $FG = H$ où $H$ est le polynôme associé au vecteur $\frac{1}{n} DFT_{ω^{- 1}} (DFT_{ω} (f) \cdot DFT_{ω} (g))$ .

Démonstration. Comme $de g (FG) < n$ , on a $FG = H = \sum_{i = 1}^{n} h_{k} X^{k}$ où $h = (h_{0}, \dots, h_{n - 1}) = f *_{n} g$ par la Proposition 6. Par le Théorème 7, on a $DFT_{ω} (h) = DFT_{ω} (f *_{n} g) = DFT_{ω} (f) \cdot DFT_{ω} (g)$ Et $DFT_{ω}^{- 1} = \frac{1}{n} DFT_{ω^{- 1}}$ par la Proposition 8. On obtient le résultat voulu. ◻

En utilisant l’algorithme écrit précédemment, on peut donc écrire un nouvel algorithme permettant de calculer le produit de deux polynômes de degré strictement inférieur à $\frac{n}{2}$ en $O (n ln (n))$ .

Algorithme 13.

# Multiplie deux polynômes de degré n.
def fast_polynomial_multiply(F, G, n, omega):
  l1 = primitive_root_powers(omega, n)
  l2 = primitive_root_powers(power(omega, n-1), n)
  prod = [fft(F, n-1, l1)[i] * fft(G, n-1, l1)[i] for i in range(n)]
  h = fft(sum(prod[k] * X^k for k in range(len(prod))), n-1, l2)
  return sum(1/n * h[k] * X^k for k in range(len(h)))

Remarque 14. On pourrait imaginer un algorithme calculant le produit de deux polynômes de degrés quelconques $n$ et $m$ sur le même modèle en considérant $F$ et $G$ comme des polynômes de degré $2^{k}$ où $k$ est tel que $2^{(k - 1)} \leq max (n, m) \leq 2^{k}$ . Il suffit ensuite de choisir $ω$ racine primitive $2^{k}$ -ième de l’unité.

Transformée de Fourier discrète