20-04-2009 Lisez-moi - Read me
 | Informatique |
Table des matières
Chapitre précédent - Chapitre suivant
Dans l'utilisation des relations de récurrence que nous avons mentionnées ci-dessus, un bon agencement des opérations à effectuer permet facilement de diminuer les temps de calculs, par exemple en sauvant des valeurs intermédiaires: si on doit calculer des termes x, x2 , x4 et x6, on a intérêt à partir de x2 pour calculer les puissances suivantes.
Ce n'est là qu'un petit gain de temps évidemment (sauf dans quelques situations particulières, telles la simulation sur ordinateur de fluides de Lenard-Jones, où l'essentiel du temps de calcul est passé dans l'évaluation des forces d'interaction entre les particules, forces dépendant justement de puissances successives d'une telle variable x).
Un exemple célèbre en science est le calcul des transformées de Fourier d'une fonction. Cette transformation permet de passer d'une représentation dans le temps à une représentation en fréquence (très utile si on cherche dans un phénomène quelconque l'une ou l'autre périodicité). Sans entrer dans les détails disons tout d'abord que l'on ramène le calcul de la transformée de Fourier à une série de Fourier. La fonction f j et sa transformée Fk sont reliées par l'expression
Il y a N termes pour la fonction fj et N termes pour la fonction Fk . Chaque terme de Fk dépend des N termes de fj . Il y a donc en tout N * N termes à évaluer.
L'idée de la transformée de Fourier rapide (FFT ou Fast Fourier Transform) repose sur la constatation que beaucoup de termes d'une estimation de F pour un k donné pourraient être regroupés. En effet, réécrivons la somme ci-dessus sous forme d'une somme de deux demi-sommes (!)
ou encore, en introduisant la fonction 
où nous avons maintenant séparé les termes
d'indice pair et les termes d'indice impair de la fonction f.
Chacune des fonctions Fk (pairs) et Fk (impairs)
comprend maintenant N/2 termes.
Nous avons remplacé le calcul de la transformée de Fourier sur N
points par deux transformées de Fourier sur N/2 points.
Considérons ce qui se passe si le nombre de points est une puissance de
2.
Nous pourrons répéter le schéma précédent en
divisant à son tour chacun des termes en deux transformées de
Fourier, chacune d'entre elles étant multipliée par le bon
facteur de phase W.
Cette opération pourra être répétée
log2 N fois. Il nous restera enfin à évaluer vraiment
la transformée de Fourier mais sur deux points, ce qui se résume
à une somme de deux termes. Pour les N points de la fonction F, nous
aurons à effectuer en tout de l'ordre de N log2 N au lieu
des N2 opérations si nous avions fait le calcul de
manière directe.
Cette méthode de "Fast Fourier Transform" est à présent répandue partout que ce soit sous forme de programme tout fait, ou même sous forme de circuits électroniques câblés qui fournissent directement les coefficients Fk.
Ils sont généralement donnés (vendus) dans une forme directement intégrable à un programme bien écrit, sous forme de modules, de procédures ou routines.
Parmi les nombreuses librairies existantes sur le marché, il faut citer
NAG, ou encore IMSL, également les librairies du CERN et celles que
chaque centre de calcul peut mettre à la disposition des utilisateurs.
On veillera à consulter avant l'emploi de telle ou telle routine, les
domaines spécifiques d'utilisation, les limites, le type
d'approximation mise en oeuvre, etc... Les descriptifs et modes d'emploi sont
généralement accessibles dans les centres de calcul et dans les
bibliothèques.
Compte tenu du fait que les librairies fournissent des routines fort
générales, censées pouvoir traiter des cas très
variés, on aura néanmoins parfois intérêt à
réécrire soi-même le petit algorithme efficace, bien
adapté au problème posé, en se basant sur les bonnes
"recettes" que l'on retrouvera dans la littérature[1].
Table des matières
Chapitre précédent - Chapitre suivant