Jump to content

FFTW: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
The benchmarks are quite outdated and they are barely objective. FFTW has decent performance while others beat it. Here is a (less outdated) benchmark of only few implementations: https://github.com/project-gemmi/benchmarking-fft/ .
Tag: references removed
QB2k (talk | contribs)
139 edits
Updated rotted link to MIT TLO FFTW webpage; restored MATLAB source that was erroneously replaced in my 2023-02-07 edit
 
(7 intermediate revisions by 7 users not shown)
Line 10: Line 10:
| developer = Matteo Frigo and [[Steven G. Johnson]]
| developer = Matteo Frigo and [[Steven G. Johnson]]
| released = {{Start date|1997|03|24|df=yes}}
| released = {{Start date|1997|03|24|df=yes}}
| latest release version = 3.3.9
| latest release version = {{wikidata|property|edit|reference|P348}}
| latest release date = {{Start date and age|2020|12|13|df=yes}}
| latest release date = {{start date and age|{{wikidata|qualifier|P348|P577}}}}
| operating system =
| operating system =
| platform =
| platform =
Line 18: Line 18:
| license = [[GPL]], commercial
| license = [[GPL]], commercial
}}
}}
The '''Fastest Fourier Transform in the West''' ('''FFTW''') is a software [[library (computer science)|library]] for computing [[discrete Fourier transform]]s (DFTs) developed by Matteo Frigo and [[Steven G. Johnson]] at the [[Massachusetts Institute of Technology]].<ref name="Frigo2005">{{cite journal |vauthors=Frigo M, Johnson SG |url=http://www.fftw.org/fftw-paper-ieee.pdf |title=The design and implementation of FFTW3 |journal=Proceedings of the IEEE |volume=93 |issue=2 |date=February 2005 |pages=216–231 |doi=10.1109/JPROC.2004.840301|citeseerx=10.1.1.66.3097 }}</ref><ref name="Frigo1998">{{cite book |vauthors=Frigo M, Johnson SG |title=FFTW: an adaptive software architecture for the FFT |journal=Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing |volume=3 |pages=1381–1384 |year=1998 |doi=10.1109/ICASSP.1998.681704|isbn=978-0-7803-4428-0 |citeseerx=10.1.1.47.8661 }}</ref><ref name="Johnson08">{{cite book |vauthors=Johnson SG, Frigo M |chapter-url=http://cnx.org/content/m16336/ |chapter=ch.11: Implementing FFTs in practice |title=Fast Fourier Transforms |editor=C. S. Burrus |publisher=Rice University |location=Houston TX: Connexions |date=September 2008}}</ref>
The '''Fastest Fourier Transform in the West''' ('''FFTW''') is a software [[library (computer science)|library]] for computing [[discrete Fourier transform]]s (DFTs) developed by Matteo Frigo and [[Steven G. Johnson]] at the [[Massachusetts Institute of Technology]].<ref name="Frigo2005">{{cite journal |vauthors=Frigo M, Johnson SG |url=http://www.fftw.org/fftw-paper-ieee.pdf |title=The design and implementation of FFTW3 |journal=Proceedings of the IEEE |volume=93 |issue=2 |date=February 2005 |pages=216–231 |doi=10.1109/JPROC.2004.840301|citeseerx=10.1.1.66.3097 |s2cid=6644892 }}</ref><ref name="Frigo1998">{{cite book |vauthors=Frigo M, Johnson SG |title=Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181) |chapter=FFTW: An adaptive software architecture for the FFT |volume=3 |pages=1381–1384 |year=1998 |doi=10.1109/ICASSP.1998.681704|isbn=978-0-7803-4428-0 |citeseerx=10.1.1.47.8661 |s2cid=12560207 }}</ref><ref name="Johnson08">{{cite book |vauthors=Johnson SG, Frigo M |chapter-url=http://cnx.org/content/m16336/ |chapter=ch.11: Implementing FFTs in practice |title=Fast Fourier Transforms |editor=C. S. Burrus |publisher=Rice University |location=Houston TX: Connexions |date=September 2008}}</ref>


FFTW is one of the fastest [[free software]] implementations of the [[fast Fourier transform]] (FFT). Like many other implementations, it can compute transforms of real and [[complex number|complex]]-valued arrays of arbitrary size and dimension in [[Big O notation|O]]([[Linearithmic function|''n''&nbsp;log&nbsp;''n'']]) time.
FFTW is one of the fastest [[free software]] implementations of the [[fast Fourier transform]] (FFT). It implements the FFT algorithm for real and [[complex number|complex]]-valued arrays of arbitrary size and dimension.


==Library==
==Library==
FFTW expeditiously transforms data by supporting a variety of algorithms and choosing the one (a particular decomposition of the transform into smaller transforms) it [[heuristic (computer science)|estimates]] or measures to be preferable in the particular circumstances. It works best on arrays of sizes with small [[prime factor]]s, with [[power of two|powers of two]] being optimal and large [[prime number|prime]]s being worst case (but still [[Big O notation|O]]([[Linearithmic function|n log n]])). To decompose transforms of [[composite number|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 FFT algorithm|Rader's]] or [[Bluestein's FFT algorithm]].<ref name="Frigo2005"/> Once the transform has been broken up into subtransforms of sufficiently small sizes, FFTW uses [[hard-coded]] [[Loop unwinding|unrolled]] FFTs for these small sizes that were produced (at [[compile time]], not at [[run time (program lifecycle phase)|run time]]) by [[automatic programming|code generation]]; these routines use a variety of algorithms including Cooley–Tukey variants, Rader's algorithm, and [[prime-factor FFT algorithm]]s.<ref name="Frigo2005"/>
FFTW expeditiously transforms data by supporting a variety of algorithms and choosing the one (a particular decomposition of the transform into smaller transforms) it [[heuristic (computer science)|estimates]] or measures to be preferable in the particular circumstances. It works best on arrays of sizes with small [[prime factor]]s, with [[power of two|powers of two]] being optimal and large [[prime number|prime]]s being worst case (but still [[Big O notation|O]]([[Linearithmic function|n log n]])). To decompose transforms of [[composite number|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 FFT algorithm|Rader's]] or [[Bluestein's FFT algorithm]].<ref name="Frigo2005"/> Once the transform has been broken up into subtransforms of sufficiently small sizes, FFTW uses [[hard-coded]] [[Loop unwinding|unrolled]] FFTs for these small sizes that were produced (at [[compile time]], not at [[run time (program lifecycle phase)|run time]]) by [[automatic programming|code generation]]; these routines use a variety of algorithms including Cooley–Tukey variants, Rader's algorithm, and [[prime-factor FFT algorithm]]s.<ref name="Frigo2005"/>


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 (computing)|platform]]. These measurements, which the authors refer to as "wisdom", can be stored in a file or string for later use.
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 [[computing platform|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 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).
Line 31: Line 31:
FFTW has limited support for ''out-of-order transforms'' (using the [[Message Passing Interface]] (MPI) version). The [[Cooley–Tukey FFT algorithm#Data reordering, bit reversal, and in-place algorithms|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 has limited support for ''out-of-order transforms'' (using the [[Message Passing Interface]] (MPI) version). The [[Cooley–Tukey FFT algorithm#Data reordering, bit reversal, and in-place algorithms|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]]<ref>{{Cite web | url=http://technology.mit.edu/technologies/15054_fastest-fourier-transform-in-the-west-fftw-version-3-3-x-fftw-v-3-3-x | title=View Technologies &#124; MIT Technology Licensing Office}}</ref> and is used in the commercial [[MATLAB]]<ref>[http://www.mathworks.com/company/newsletters/articles/faster-finite-fourier-transforms-matlab.html Faster Finite Fourier Transforms: MATLAB 6 incorporates FFTW]</ref> matrix package for calculating FFTs. FFTW is written in the [[C (programming language)|C]] language, but [[Fortran]] and [[Ada (programming language)|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 '<code>genfft</code>', which is written in [[OCaml]].<ref name="FFTW FAQ">[http://www.fftw.org/faq/section2.html#languages "FFTW FAQ"]</ref>
FFTW is licensed under the [[GNU General Public License]]. It is also licensed commercially (for a cost of up to $12,500) by [[MIT]]<ref>{{Cite web |title=FFTW - Fastest Fourier Transform in the West {{!}} MIT Technology Licensing Office |url=https://tlo.mit.edu/technologies/fftw-fastest-fourier-transform-west |access-date=2023-02-07 |website=tlo.mit.edu}}</ref> and is used in the commercial [[MATLAB]]<ref>{{Cite web |title=Faster Finite Fourier Transforms MATLAB |url=https://www.mathworks.com/company/technical-articles/faster-finite-fourier-transforms-matlab.html |access-date=2014-03-24 |website=www.mathworks.com |language=en}}</ref> matrix package for calculating FFTs. FFTW is written in the [[C (programming language)|C]] language, but [[Fortran]] and [[Ada (programming language)|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 '<code>genfft</code>', which is written in [[OCaml]].<ref name="FFTW FAQ">[http://www.fftw.org/faq/section2.html#languages "FFTW FAQ"]</ref>


In 1999, FFTW won the [[J. H. Wilkinson Prize for Numerical Software]].
In 1999, FFTW won the [[J. H. Wilkinson Prize for Numerical Software]].
Line 44: Line 44:
==External links==
==External links==
* {{Official website}}
* {{Official website}}

{{ML programming}}


{{DEFAULTSORT:Fftw}}
{{DEFAULTSORT:Fftw}}
Line 51: Line 53:
[[Category:Free mathematics software]]
[[Category:Free mathematics software]]
[[Category:Massachusetts Institute of Technology software]]
[[Category:Massachusetts Institute of Technology software]]
[[Category:Software using the GPL license]]

Latest revision as of 21:02, 25 June 2024

FFTW
Developer(s)Matteo Frigo and Steven G. Johnson
Initial release24 March 1997 (1997-03-24)
Stable release
3.3.10[1] Edit this on Wikidata / 15 September 2021; 3 years ago (15 September 2021)
Repository
Written inC, OCaml
TypeNumerical software
LicenseGPL, commercial
Websitewww.fftw.org Edit this on Wikidata

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 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. ^ "FFTW - Fastest Fourier Transform in the West | MIT Technology Licensing Office". tlo.mit.edu. Retrieved 2023-02-07.
  6. ^ "Faster Finite Fourier Transforms MATLAB". www.mathworks.com. Retrieved 2014-03-24.
  7. ^ "FFTW FAQ"
[edit]
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=FFTW&oldid=1230991906"