fbpx
Wikipedia

FFTW

December 20, 2023

The Fastest Fourier Transform in the West (FFTW) is a software library for computing discrete Fourier transforms (DFTs) developed by Matteo Frigo and Steven G. Johnson at the Massachusetts Institute of Technology.[2][3][4]

FFTW
The FFTW logo
Developer(s)Matteo Frigo and Steven G. Johnson
Initial release24 March 1997 (1997-03-24)
Stable release
3.3.10[1]  / 15 September 2021; 2 years ago (15 September 2021)
Repository
  • github.com/FFTW/fftw3
Written inC, OCaml
TypeNumerical software
LicenseGPL, commercial
Websitewww.fftw.org 

FFTW is one of the fastest free software implementations of the fast Fourier transform (FFT). It implements the FFT algorithm for real and complex-valued arrays of arbitrary size and dimension.

Library edit

FFTW expeditiously transforms data by supporting a variety of algorithms and choosing the one (a particular decomposition of the transform into smaller transforms) it estimates or measures to be preferable in the particular circumstances. It works best on arrays of sizes with small prime factors, with powers of two being optimal and large primes being worst case (but still O(n log n)). To decompose transforms of composite sizes into smaller transforms, it chooses among several variants of the Cooley–Tukey FFT algorithm (corresponding to different factorizations and/or different memory-access patterns), while for prime sizes it uses either Rader's or Bluestein's FFT algorithm.[2] Once the transform has been broken up into subtransforms of sufficiently small sizes, FFTW uses hard-coded unrolled FFTs for these small sizes that were produced (at compile time, not at run time) by code generation; these routines use a variety of algorithms including Cooley–Tukey variants, Rader's algorithm, and prime-factor FFT algorithms.[2]

For a sufficiently large number of repeated transforms it is advantageous to measure the performance of some or all of the supported algorithms on the given array size and platform. These measurements, which the authors refer to as "wisdom", can be stored in a file or string for later use.

FFTW has a "guru interface" that intends "to expose as much as possible of the flexibility in the underlying FFTW architecture". This allows, among other things, multi-dimensional transforms and multiple transforms in a single call (e.g., where the data is interleaved in memory).

FFTW has limited support for out-of-order transforms (using the Message Passing Interface (MPI) version). The data reordering incurs an overhead, which for in-place transforms of arbitrary size and dimension is non-trivial to avoid. It is undocumented for which transforms this overhead is significant.

FFTW is licensed under the GNU General Public License. It is also licensed commercially (for a cost of up to $12,500) by MIT[5] and is used in the commercial MATLAB[6] matrix package for calculating FFTs. FFTW is written in the C language, but Fortran and Ada interfaces exist, as well as interfaces for a few other languages. While the library itself is C, the code is actually generated from a program called 'genfft', which is written in OCaml.[7]

In 1999, FFTW won the J. H. Wilkinson Prize for Numerical Software.

See also edit

References edit

  1. ^ "The FFTW Release Notes". Retrieved 16 September 2021.
  2. ^ a b c Frigo M, Johnson SG (February 2005). "The design and implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.
  3. ^ Frigo M, Johnson SG (1998). "FFTW: An adaptive software architecture for the FFT". Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181). Vol. 3. pp. 1381–1384. CiteSeerX 10.1.1.47.8661. doi:10.1109/ICASSP.1998.681704. ISBN 978-0-7803-4428-0. S2CID 12560207.
  4. ^ Johnson SG, Frigo M (September 2008). "ch.11: Implementing FFTs in practice". In C. S. Burrus (ed.). Fast Fourier Transforms. Houston TX: Connexions: Rice University.
  5. ^ "View Technologies | MIT Technology Licensing Office".
  6. ^ "FFTW - Fastest Fourier Transform in the West | MIT Technology Licensing Office". tlo.mit.edu. Retrieved 2023-02-07.
  7. ^ "FFTW FAQ"

External links edit

  • Official website  

December 20, 2023
fftw, this, article, rely, excessively, sources, closely, associated, with, subject, potentially, preventing, article, from, being, verifiable, neutral, please, help, improve, replacing, them, with, more, appropriate, citations, reliable, independent, third, p. This article may rely excessively on sources too closely associated with the subject potentially preventing the article from being verifiable and neutral Please help improve it by replacing them with more appropriate citations to reliable independent third party sources April 2018 Learn how and when to remove this template message The Fastest Fourier Transform in the West FFTW is a software library for computing discrete Fourier transforms DFTs developed by Matteo Frigo and Steven G Johnson at the Massachusetts Institute of Technology 2 3 4 FFTWThe FFTW logoDeveloper s Matteo Frigo and Steven G JohnsonInitial release24 March 1997 1997 03 24 Stable release3 3 10 1 15 September 2021 2 years ago 15 September 2021 Repositorygithub wbr com wbr FFTW wbr fftw3Written inC OCamlTypeNumerical softwareLicenseGPL commercialWebsitewww wbr fftw wbr org FFTW is one of the fastest free software implementations of the fast Fourier transform FFT It implements the FFT algorithm for real and complex valued arrays of arbitrary size and dimension Contents 1 Library 2 See also 3 References 4 External linksLibrary editFFTW expeditiously transforms data by supporting a variety of algorithms and choosing the one a particular decomposition of the transform into smaller transforms it estimates or measures to be preferable in the particular circumstances It works best on arrays of sizes with small prime factors with powers of two being optimal and large primes being worst case but still O n log n To decompose transforms of composite sizes into smaller transforms it chooses among several variants of the Cooley Tukey FFT algorithm corresponding to different factorizations and or different memory access patterns while for prime sizes it uses either Rader s or Bluestein s FFT algorithm 2 Once the transform has been broken up into subtransforms of sufficiently small sizes FFTW uses hard coded unrolled FFTs for these small sizes that were produced at compile time not at run time by code generation these routines use a variety of algorithms including Cooley Tukey variants Rader s algorithm and prime factor FFT algorithms 2 For a sufficiently large number of repeated transforms it is advantageous to measure the performance of some or all of the supported algorithms on the given array size and platform These measurements which the authors refer to as wisdom can be stored in a file or string for later use FFTW has a guru interface that intends to expose as much as possible of the flexibility in the underlying FFTW architecture This allows among other things multi dimensional transforms and multiple transforms in a single call e g where the data is interleaved in memory FFTW has limited support for out of order transforms using the Message Passing Interface MPI version The data reordering incurs an overhead which for in place transforms of arbitrary size and dimension is non trivial to avoid It is undocumented for which transforms this overhead is significant FFTW is licensed under the GNU General Public License It is also licensed commercially for a cost of up to 12 500 by MIT 5 and is used in the commercial MATLAB 6 matrix package for calculating FFTs FFTW is written in the C language but Fortran and Ada interfaces exist as well as interfaces for a few other languages While the library itself is C the code is actually generated from a program called genfft which is written in OCaml 7 In 1999 FFTW won the J H Wilkinson Prize for Numerical Software See also edit nbsp Free and open source software portalFFTPACKReferences edit The FFTW Release Notes Retrieved 16 September 2021 a b c Frigo M Johnson SG February 2005 The design and implementation of FFTW3 PDF Proceedings of the IEEE 93 2 216 231 CiteSeerX 10 1 1 66 3097 doi 10 1109 JPROC 2004 840301 S2CID 6644892 Frigo M Johnson SG 1998 FFTW An adaptive software architecture for the FFT Proceedings of the 1998 IEEE International Conference on Acoustics Speech and Signal Processing ICASSP 98 Cat No 98CH36181 Vol 3 pp 1381 1384 CiteSeerX 10 1 1 47 8661 doi 10 1109 ICASSP 1998 681704 ISBN 978 0 7803 4428 0 S2CID 12560207 Johnson SG Frigo M September 2008 ch 11 Implementing FFTs in practice In C S Burrus ed Fast Fourier Transforms Houston TX Connexions Rice University View Technologies MIT Technology Licensing Office FFTW Fastest Fourier Transform in the West MIT Technology Licensing Office tlo mit edu Retrieved 2023 02 07 FFTW FAQ External links editOfficial website nbsp Retrieved from https en wikipedia org w index php title FFTW amp oldid 1166739952, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.