up: Texte principal

Algorithmes rapides

L'analyse de Fourier est entrée définitivement dans l'ère moderne du calcul numérique vers le milieu des années 1960, avec l'invention de la FFT (Fast Fourier Transform), par Cooley et Tukey. Si un signal se présente sous la forme d'une suite finie de N nombres, l'évaluation directe de sa transformée de Fourier (elle aussi sous la forme d'une suite de N valeurs) nécessite un nombre d'opérations proportionnel à
Cette approche naïve n'est pas optimale, et un réarrangement astucieux de l'ordre des opérations effectuées permet de faire chuter ce nombre à
. Pour donner un ordre d'idée, le nombre d'opérations (et donc le temps de calcul) chute ainsi d'un facteur approximativement égal à 100 pour N=1000, et d'un facteur supérieur à 1000 pour N=16000. A l'instar de la transformation de Fourier, la transformation en ondelettes peut elle aussi donner lieu à des algorithmes efficaces. Ceux ci sont basés sur deux opérateurs H et G, qui effectuent des convolutions avec deux suites h(n) et g(n). Par exemple, dans le cas d'une décomposition non-redondante, c'est à dire si l'on se limite a une famille d'ondelettes formant une base orthonormée, les opérateurs H et G prennent la forme

Ces convolutions ne sont pas des convolutions ordinaires, à cause du facteur 2 intervenant dans le terme f(2n-k). Ce facteur 2 traduit le fait que la convolution est suivie d'un sous-échantillonnage. Ainsi, chaque application de ces opérateurs réduit la longueur de la suite d'un facteur 2. Si nous partons d'une suite de longueur N, et appliquons l'algorithme décrit dans la figure 3, nous obtenons ainsi