FFTW

Fiche logiciel validé
  • Création ou MAJ importante : 19/04/10
  • Correction mineure : 19/02/14
Mots-clés
Pour aller plus loin
  • Fiches logiciel PLUME connexes : SHTns

FFTW : bibliothèque effectuant des transformées de Fourier complexes ou réelles, rapides et portables

Description
Fonctionnalités générales

FFTW est une bibliothèque écrite en C de fonctions pour calculer la transformée de Fourier discrète (DFT) en une ou plusieurs dimensions, de taille arbitraire (puissance de 2 ou non), pour des données réelles ou complexes.
Elle inclut également des routines pour la transformée en cosinus ou en sinus (DCT et DST).

Ses principaux atouts sont la performance tout en maintenant une portabilité (compilation sur toutes sortes de machines) et une flexibilité (s'adapte à des arrangements de données complexes).

FFTW peut effectuer des transformées de Fourier en parallèle, sur architecture distribuée via MPI, ou bien sur architecture à mémoire partagée via OpenMP ou pthreads.

Autres fonctionnalités
  • Rapidité (support des instructions SSE/SSE2/AVX/3dNow!/Altivec).
  • Une ou plusieurs dimensions.
  • Taille arbitraire (des tailles multiples de petits nombres premiers sont plus rapides, mais FFTW utilise des algorithmes en O(N log N) même si N est un nombre premier).
  • Transformée rapide de données réelles.
  • Transformées en cosinus et sinus (DCT et DST de type I-IV).
  • Gestion efficace de transformées multiples ou vectorielles.
  • Transformées parallèles via OpenMP, pthreads ou MPI.
  • Interface Fortran et C.
Interopérabilité

Utilisable à partir de programmes en C ou en Fortran.
De plus, la transformée de Fourier de la bibliotheque intel (MKL) peut etre utilisée sans changer le code, car elle peut etre appellée via la meme interface que fftw.

Contexte d'utilisation dans mon laboratoire/service

Nous sommes plusieurs à utiliser FFTW pour les transformées de Fourier dans des codes de calcul intensif (méthodes spectrales).
C'est ce qu'il y a de plus rapide tout en restant portable (fonctionne sur des architectures intel, amd, powerpc). Sa flexibilité dans l'organisation des données et dans la taille (pas nécessairement une puissance de 2) la rend très pratique également. La précision du calcul est également optimale (double précision ou simple précision).

De plus, la transformée de Fourier de la bibliotheque intel (MKL) peut etre utilisée sans changer le code, car elle peut etre appellée via la meme interface que fftw.

Limitations, difficultés, fonctionnalités importantes non couvertes

Une petite difficulté existe pour porter du code utilisant une autre bibliothèque : la transformée de Fourier avec des données réelles calculée par FFTW stocke les coefficients de Fourier sous forme complexe, en nécessitant N/2+1 nombres complexes, car le fondamental k=0 est stocké sous forme complexe également.

Environnement du logiciel
Distributions dans lesquelles ce logiciel est intégré

La plupart des distributions qui se respectent.

Plates-formes

Toutes plates-formes avec un compilateur C.

Autres logiciels aux fonctionnalités équivalentes

Logiciels propriétaires pour une plate-forme donnée, mais ils n'implémentent en général qu'une petite partie des fonctionnalités de FFTW (par exemple intel MKL, ...)

Environnement de développement
Type de structure associée au développement

Développé au MIT

Environnement utilisateur
Documentation utilisateur
Divers (astuces, actualités, sécurité)

Une version parallèle MPI devrait voir le jour prochainement.

Commentaires

commentaire sur le commentaire ;-)

sur http://www.fftw.org/fftw3_doc/Real_002ddata-DFTs.html

on lit:

FFTW is best at handling sizes of the form
2a 3b 5c 7d 11e 13f, where e+f is either 0 or 1, and the other exponents are arbitrary.

Performance, Compilation, Mythe des 2^N

Utilisateur de la librairie FFTw pour un projet ou je suis contributeur http://www.projet-plume.org/fiche/gdl, je confirme sa très grande efficacité. Elle est environ deux fois plus rapide que la version GSL de la FFT (pour des cas classiques testés). Sur des tableaux à partir de 2^16/2^17 (usage de plus en plus fréquent), testée sur plusieurs archi et OS, FFTw dans GDL est plus rapide que la FFT fournie dans IDL http://idlastro.gsfc.nasa.gov/idl_html_help/FFT.html (qui est une référence dans notre communauté Astro).

Quoique généralement bien packagée pour les grandes distributions (telles Mandriva, CentOS, Débian et Ubuntu), si nécessaire, il faut faire attention à bien la compiler deux fois en float et double (--enable-float). Ceci produit libfftw3 et libfftw3f. La documentation n'est pas toujours évidente sur ce point.

Par ailleurs, je pense qu'il est vraiment temps d'insister auprès des étudiants et des collègues qu'en première approximation les performances des bonnes librairies de FFT suivent bien ~alpha N log2(N) avec N=2^x * 3^y * 5^z (* P^t) (en théorie avec des radicaux P premiers, il vaut mieux éviter les P "grands") et pas seulement 2^x (on pourra trouver une expression de alpha dans le lien ci-dessous). Si z ou t sont petits par rapport à x et y, le surcoût est souvent infime. Ceci est vérifié avec FFTw comme avec la FFT fournie par IDL (depuis longtemps). Ceci présente réellement des avantages pratiques pour traiter des séries de données longues se coupant mal en bloc de taille fixe en 2^M (on n'a pas toujours liberté du taux d'échantillonnage et de la durée d'intégration, il peut être agaçant de devoir réduire de presque un facteur 2 pour retomber sur un 2^x !).