Diviser pour régner (suite) - documents.lamacs.frdocuments.lamacs.fr/cours/macs1/infochap5s.pdf ·...

1

Chapitre 5

Diviser pour régner(suite)

Convolution et FFT

FFT = Fast Fourier Transform(Transformée de Fourier rapide)

3

FFT : Applications

Applications.■ Optique, acoustique, physique quantique, télécommunications,

systèmes de contrôle, traitement du signal, reconnaissance de la parole, compression de données, traitement des images.

■ Lecture DVD, JPEG, MP3, MRI, CAT.■ Solutions numériques de l’équation de Poisson.

The FFT is one of the truly great computational developments of this [20th] century. It has changed the face of science and engineering so much that it is not an exaggeration to say that life as we know it would be very different without the FFT. -Charles van Loan

4

FFT : un peu d’histoire

Gauss (1805, 1866). Analyse du mouvement périodique de Céres.

Runge-König (1924). Fondations théoriques.

Danielson-Lanczos (1942). Algorithme efficace.

Cooley-Tukey (1965). Utilisé pour le contrôle des tests nucléaires en URSS et pour le pistage des sous-marins. FFT redécouvert et rendu populaire.

L’ importance de FFT ne fut pleinement reconnue qu’avec l’utilisation massive des ordinateurs.

5

Polynômes : représentation par coefficients

Polynôme. [représentation par coefficients]

Addition : O(n) opérations arithmétiques.

Evaluation : O(n) opérations arithmétiques (méthode de Horner.)

Multiplication (convolution) : O(n2) en utilisant la méthode brutale.

A x =a0a1 xa2x2Lan−1 x

n−1

B x =b0b1 xb2 x2Lbn−1x

n−1

A x B x =a0b0 a1b1 xLan−1bn−1 xn−1

A x =a0 x a1x a2Lx an−2x an−1 L

A x ´ B x = ∑i=0

2n−2

c i xi , where c i=∑

j=0

i

a jbi− j

6

Polynômes : représentation par couples (point,valeur)

Théorème fondamental de l’algèbre. [Gauss] Un polynôme de degré n à coefficients complexes a n racines complexes (avec multiplicités.)

Corollaire. Un polynôme de degré n-1 A(x) est entièrement déterminé par son évaluation en n valeurs distinctes de x.

x

y

xj

yj = A(xj)

7

Polynômes : représentation par couples (point,valeur)

Polynôme. [représentation points-valeurs]

Addition : O(n) opérations arithmétiques.

Multiplication : O(n), mais 2n-1 points sont nécessaires.

Evaluation : O(n2), en utilisant la formule de Lagrange.

A x : x0 , y0 ,K , xn-1 , yn−1

B x : x0 , z0 ,K , xn-1 ,zn−1

A x B x : x0 , y0z0 ,K , xn-1 , yn−1zn−1

A x =∑k=0

n−1

yk

∏j¹k

x−x j

∏j¹k

x k−x j

A x ´ B x : x0 ,y0´ z0 ,K , x2n-1 ,y2n−1´ z2n−1

8

Passage d’une représentation à l’autre

Compromis. Évaluation rapide ou multiplication rapide. On veut les deux !

But. Rendre toutes les opérations rapides en permettant des conversions efficaces entre les deux représentations.

Coefficients

Représentation

O(n2)

Multiplication

O(n)

Evaluation

Points-valeurs O(n) O(n2)

a0 ,a1 ,K ,an-1 x0 , y0 ,K , xn−1 , yn−1

représentation par coefficients

représentation parpoints-valeurs

9

Passage d’une représentation à l’autre : méthode brutale

Coefficients vers Points-valeurs. Étant donné un polynôme a0 + a1 x + ... + an-1 xn-1, l’évaluer en n points distincts x0, ... , xn-1.

Points-valeurs vers Coefficients. Étant donnés n points distincts x0, ..., xn-1 et n valeurs y0, ..., yn-1, trouver l’unique polynôme A(x) = a0 + a1 x + ... + an-1 xn-1 tel que A(xi) = yi, pour i = 1,…, n-1 .

[y0

y1

y2

Myn−1

]=[1 x0 x0

2 L x0n−1

1 x1 x12 L x1

n−1

1 x2 x22 L x2

n−1

M M M O M1 xn−1 xn−1

2 L xn−1n−1

][a0

a1

a2

Man−1

]la matrice de Vandermonde est inversible ssi les xi sont deux à deux distincts

O(n3) pour l’élimination de Gauss

O(n2) pour la multiplication matrice x vecteur

10

Coefficient vers points-valeurs : intuition

Coefficients vers Points-valeurs. Étant donné un polynôme a0 + a1 x + ... + an-1 xn-1, l’évaluer en n points distincts x0, ... , xn-1.

Divide. Casser le polynôme selon la parité des puissances.■ A(x) = a0 + a1x + a2x2 + a3x3 + a4x4 + a5x5 + a6x6 + a7x7.■ Aeven(x) = a0 + a2x + a4x2 + a6x3.■ Aodd (x) = a1 + a3x + a5x2 + a7x3.■ A(-x) = Aeven(x2) + x Aodd(x2).■ A(-x) = Aeven(x2) - x Aodd(x2).

Intuition. On choisit les deux points ±1.■ A(-1) = Aeven(1) + 1 Aodd(1). ■ A(-1) = Aeven(1) - 1 Aodd(1). Pour évaluer un polynôme de degré ≤ n

en 2 points, il suffit d’évaluer deux polynômes de degré ≤ ½n en 1 point.

11

Coefficient vers points-valeurs : intuition

Coefficients vers Points-valeurs. Étant donné un polynôme a0 + a1 x + ... + an-1 xn-1, l’évaluer en n points distincts x0, ... , xn-1.

Divide. Casser le polynôme selon la parité des puissances.■ A(x) = a0 + a1x + a2x2 + a3x3 + a4x4 + a5x5 + a6x6 + a7x7.■ Aeven(x) = a0 + a2x + a4x2 + a6x3.■ Aodd (x) = a1 + a3x + a5x2 + a7x3.■ A(-x) = Aeven(x2) + x Aodd(x2).■ A(-x) = Aeven(x2) - x Aodd(x2).

Intuition. On choisit les quatre points ±1, ±i.■ A(-1) = Aeven(-1) + 1 Aodd( 1). ■ A(-1) = Aeven(-1) - 1 Aodd(-1).■ A(-i) = Aeven(-1) + i Aodd(-1). ■ A(-i) = Aeven(-1) - i Aodd(-1).

Pour évaluer un polynôme de degré ≤ nen 4 points, il suffit d’évaluer deux polynômess de degré ≤ ½n en 2 points.

12

Transformée de Fourier discrète

Coefficients vers Points-valeurs. Étant donné un polynôme a0 + a1 x + ... + an-1 xn-1, l’évaluer en n points distincts x0, ... , xn-1.

Idée clé : choisir xk = ωk où ω est la ne racine principale de l’unité.

Transformée de Fourier discrète

[y0

y1

y2

y3

Myn−1

]=[1 1 1 1 L 11 w1 w2 w3 L wn−1

1 w2 w4 w6 L w2 n−1

1 w3 w6 w9 L w3 n−1

M M M M O M1 wn−1 w2 n−1 w3 n−1 L wn−1 n−1

] [a0

a1

a2

a3

Man−1

]Matrice de Fourier Fn

13

Rappel sur les racines de l’unité

Déf. Une ne racine de l’unité est un nombre complexe x tel que xn = 1.

Fait. Les ne racines de l’ unité sont : ω0, ω1, …, ωn-1 où ω = e 2π i / n.Preuve. (ωk)n = (e 2π i k / n) n = (e π i ) 2k = (-1) 2k = 1.

Fait. Les ½ne racines de l’ unité sont : ν0, ν1, …, νn/2-1 où ν = e 4π i / n.Fait. ω2 = ν et (ω2)k = νk.

ω0 = ν0 = 1

ω1

ω2 = ν1 = i

ω3

ω4 = ν2 = -1

ω5

ω6 = ν3 = -i

ω7

n = 8

14

Transformée de Fourier rapide

But. Evaluer un polynôme de degré n-1 A(x) = a0 + ... + an-1 xn-1 en les ne racines de l’unité : ω0, ω1, …, ωn-1.

Divide. Casser le polynôme selon la parité des puissances.■ Aeven(x) = a0 + a2x + a4x2 + … + an/2-2 x(n-1)/2.■ Aodd (x) = a1 + a3x + a5x2 + … + an/2-1 x(n-1)/2.■ A(x) = Aeven(x2) + x Aodd(x2).

Conquer. Évaluer Aeven(x) et Aodd(x) en les ½ne racines de l’unité : ν0, ν1, …, νn/2-1.

Combiner. ■ A(ωk+n) = Aeven(νk) + ωk Aodd(νk), 0 ≤ k < n/2■ A(ωk+n) = Aeven(νk) - ωk Aodd(νk), 0 ≤ k < n/2

ωk+n = -ωk

νk = (ωk)2 = (ωk+n)2

15

fft(n, a0,a1,…,an-1) {

si (n == 1) retourner a0

(e0,e1,…,en/2-1) ← FFT(n/2, a0,a2,a4,…,an-2)

(d0,d1,…,dn/2-1) ← FFT(n/2, a1,a3,a5,…,an-1)

pour k = 0 à n/2 - 1 {

ωk ← e2πik/n

yk+n/2 ← ek + ωk dk

yk+n/2 ← ek - ωk dk

}

retourner (y0,y1,…,yn-1)

}

FFT : l’algorithme

16

FFT : résumé

Théorème. L’algorithme FFT évalue un polynôme de degré n-1 en chacune des ne racines de l’unité, en O(n log n) étapes de calcul.

Temps d’exécution. T(2n) = 2T(n) + O(n) ⇒ T(n) = O(n log n).

on suppose que n est une puissance de 2

a0 ,a1 ,K ,an-1 w0 , y0 ,K , wn−1 , yn−1

O(n log n)

représentation parcoefficients

représentation parpoints-valeurs

17

Arbre de récursion

a0, a1, a2, a3, a4, a5, a6, a7

a1, a3, a5, a7a0, a2, a4, a6

a3, a7a1, a5a0, a4 a2, a6

a0 a4 a2 a6 a1 a5 a3 a7

ordre "bit-reversed"

000 100 010 110 001 101 011 111

shuffle “parfait”

18

Points-valeurs vers Coefficients : transformée de Fourier discrète inverse

But. Étant données les valeurs y0, ... , yn-1, trouver l’unique polynôme A(x) = a0 + a1 x + ... + an-1 xn-1 tel que A(ωi) = yi , i = 0, …, n-1.

DFT (transformé de Fourier discrète) inverse

[a0

a1

a2

a3

Man−1

]=[1 1 1 1 L 11 w1 w2 w3 L wn−1

1 w2 w4 w6 L w2 n−1

1 w3 w6 w9 L w3 n−1

M M M M O M1 wn−1 w2 n−1 w3 n−1 L w n−1 n−1

] −1

[y0

y1

y2

y3

Myn−1

]Matrice de Fourier inverse (Fn)-1

19

Propriété. La matrice de Fourier inverse est donnée par la formule suivante :

Conséquence. Pour calculer la transformée de Fourier inverse, on reprend l’algorithme FFT en utilisant ω-1 = e -2π i / n comme ne racine principale de l’unité (et on divise par n).

Gn=1n [

1 1 1 1 L 11 w−1 w−2 w−3 L w−n−1

1 w−2 w−4 w−6 L w−2 n−1

1 w−3 w−6 w−9 L w−3 n−1

M M M M O M1 w− n−1 w−2 n−1 w−3 n−1 L w−n−1 n−1

]

FFT inverse

20

FFT inverse : preuve de correction

Proposition. Fn et Gn sont inverses l’une de l’autre.Preuve.

Lemme de sommation. Soit ω une ne racine primitive de l’unité. Alors

Preuve.■ Si k est un multiple de n, alors ωk = 1 ⇒ la somme vaut n.■ Chaque ωk est une racine de xn - 1 = (x - 1) (1 + x + x2 + ... + xn-1).■ Si ωk ≠ 1 on a : 1 + ωk + ωk(2) + . . . + ωk(n-1) = 0 ⇒ la somme 0. ▪

∑j=0

n−1

wkj={n if kº0modn0 otherwise

FnGn kk '=1n∑j=0

n−1

wkjw− j k '

= 1n∑j=0

n−1

w k−k ' j= {1 if k=k '

0 otherwisecf. lemme de sommation ci-dessous

21

FFT inverse : l’algorithme

ffti(n, a0,a1,…,an-1) {

si (n == 1) retourner a0

(e0,e1,…,en/2-1) ← FFT(n/2, a0,a2,a4,…,an-2)

(d0,d1,…,dn/2-1) ← FFT(n/2, a1,a3,a5,…,an-1)

pour k = 0 à n/2 - 1 {

ωk ← e-2πik/n

yk+n/2 ← (ek + ωk dk) / n

yk+n/2 ← (ek - ωk dk) / n

}

retourner (y0,y1,…,yn-1)

}

22

FFT inverse : résumé

Théorème. L’algorithme FFT inverse interpole un polynôme de degré ≤ n-1 étant données les valeurs prises en chacune des ne racines de l’unité, en O(n log n) étapes de calcul.

on suppose que n est une puissance de 2

a0 ,a1 ,K ,an-1 w0 , y0 ,K , wn−1 , yn−1

O(n log n)

représentation parcoefficients

O(n log n) représentation parpoints-valeurs

23

Multiplication de polynômes

Théorème. On multiplier deux polynômes de degré n-1 en O(n log n) étapes de calcul.

a0 ,a1 ,K ,an-1

b0 ,b1 ,K ,bn-1c0 ,c1 , K ,c2n-2

A x0 ,K , A x2n-1

B x0 ,K ,B x2n-1C x0 ,C x1 ,K ,C x2n-1O(n)

Multiplication points-valeurs

O(n log n)FFT inverse FFT O(n log n)

représentation par coefficients représentation par

coefficients

24

FFT en pratique

“Fastest Fourier transform in the West.” [Frigo & Johnson]■ Bibliothèque C optimisée.■ Contient : DFT, DCT, réel, complexe, en dimension quelconque.■ Prix Wilkinson 1999 du logiciel numérique.■ Portable et compétitif.

Détails d’implémentation.■ Au lieu d’exécuter un algorithme prédéterminé, il évalue le matériel

et utilise un compilateur dédié pour engendrer un code optimisé adapté à la “forme” du problème.

■ Le coeur de l’algorithme est une version itérative du FFT binaire de Cooley-Tukey.

■ O(n log n), même si la dimension est un nombre premier.Référence: http://www.fftw.org

25

Multiplication entière

Multiplication entière. Étant donnés deux entiers de n bits a = an-1 … a1a0 et b = bn-1 … b1b0, calculer leur produit c = a × b.

Algorithme (convolution).■ On utilise deux polynômes A(x) et B(x) : a = A(2), b = B(2).■ On calcule C(x) = A(x) × B(x).■ On évalue C(2) = a × b.■ Temps d’exécution: O(n log n) opérations arithmétiques complexes.

Théorème. [Schönhage-Strassen 1971] O(n log n log log n) opérations binaires.

En pratique. [GNU Multiple Precision Arithmetic Library] GMP prétend être "the fastest bignum library on the planet." Elle utilise un algorithme brutal, Karatsuba, ou FFT, selon la dimension du problème.

A x =a0a1 xa2x2Lan−1 x

n−1

B x =b0b1 xb2 x2Lbn−1x

n−1

Un petit extra

27

Décomposition de la matrice de Fourier

Décomposition de la matrice de Fourier.

y=Fna=[ In /2 Dn/2

In /2 −Dn/2 ][Fn /2aevenFn /2aodd ]

I4=[1 0 0 00 1 0 00 0 1 00 0 0 1

]

D4=[w0 0 0 00 w1 0 00 0 w2 00 0 0 w3 ]

Fn=[1 1 1 1 L 11 w1 w2 w3 L wn−1

1 w2 w4 w6 L w2 n−1

1 w3 w6 w9 L w3 n−1

M M M M O M1 wn−1 w2 n−1 w3 n−1 L wn−1 n−1

]Fn=[In /2 Dn /2

In /2 −Dn /2 ][F n/2 0

0 Fn /2 ]PnT

P4=[1 0 0 00 0 1 00 1 0 00 0 0 1

]