OpenStax CNX

Sections
You are here: Home » Content » Implementing FFTs in Practice

About: Implementing FFTs in Practice

Module by: Steven G. Johnson, Matteo Frigo. E-mail the authors

View the content: Implementing FFTs in Practice

Metadata

Name: Implementing FFTs in Practice
ID: m16336
Language: English (en)
Summary: Discussion of the considerations involved in high-performance FFT implementations, which center largely on memory access and other non-arithmetic concerns, as illustrated by a case study of the FFTW library.
Subject: Mathematics and Statistics
Keywords: cache, cache-oblivious algorithm, code generation, Fastest Fourier Transform in the West, FFT, FFTW, self-optimization
License: Creative Commons Attribution License CC-BY 3.0

Authors: Steven G. Johnson (stevenj@math.mit.edu), Matteo Frigo (athena@fftw.org)
Copyright Holders: Steven G. Johnson (stevenj@math.mit.edu)
Maintainers: Steven G. Johnson (stevenj@math.mit.edu), C. Sidney Burrus (csb@rice.edu), Daniel Williamson (dcwill@cnx.org)

Latest version: 1.15 (history)
First publication date: May 27, 2008 1:25 pm -0500
Last revision to module: May 4, 2012 10:17 pm -0500

Downloads

PDF: m16336_1.15.pdf PDF file, for viewing content offline and printing. Learn more.
XML: m16336_1.15.cnxml XML that defines the structure and contents of the module, minus any included media files. Can be reimported in the editing interface. Learn more.

Version History

Version: 1.15 May 4, 2012 10:17 pm -0500 by C. Sidney Burrus
Changes:
new license

Version: 1.14 Sep 18, 2009 4:37 pm -0500 by Daniel Williamson
Changes:
added google analytics tracking code

Version: 1.13 Jul 7, 2009 9:44 am -0500 by Daniel Williamson
Changes:
accessibility, links, and math fixes

Version: 1.12 Apr 3, 2009 10:00 pm -0500 by C. Sidney Burrus
Changes:
New version of Cnxml

Version: 1.11 Sep 11, 2008 4:49 pm -0500 by C. Sidney Burrus
Changes:
added Matteo as author

Version: 1.10 Aug 6, 2008 10:05 am -0500 by Steven G. Johnson
Changes:
update the metadata

Version: 1.9 Aug 6, 2008 9:56 am -0500 by Steven G. Johnson
Changes:
hyperlinks and small fixes related to previous section move

Version: 1.8 Aug 5, 2008 9:11 pm -0500 by Steven G. Johnson
Changes:
fixed numerous small typographical errors, moved section on generality towards top and reworked into an introduction to the goals and background of FFTW, added some clarifications to the section on numerical accuracy

Version: 1.7 Jul 25, 2008 2:28 pm -0500 by C. Sidney Burrus
Changes:
role change

Version: 1.6 Jul 25, 2008 8:36 am -0500 by C. Sidney Burrus
Changes:
roles

Version: 1.5 Jul 24, 2008 5:52 pm -0500 by C. Sidney Burrus
Changes:
correcting roles
making Johnson the author

Version: 1.4 Jul 18, 2008 11:46 am -0500 by C. Sidney Burrus
Changes:
added Johnson as the author

Version: 1.3 Jul 18, 2008 10:08 am -0500 by Daniel Williamson
Changes:
image and role corrections

Version: 1.2 Jun 4, 2008 4:14 pm -0500 by Daniel Williamson
Changes:
established inter-module CNXNs

Version: 1.1 Jun 2, 2008 11:38 am -0500 by Daniel Williamson
Changes:
none

How to Reuse and Attribute This Content

If you derive a copy of this content using a OpenStax-CNX account and publish your version, proper attribution of the original work will be automatically done for you.

If you reuse this work elsewhere, in order to comply with the attribution requirements of the license (CC-BY 3.0), you must include

  • the authors' names: Steven Johnson, Matteo Frigo
  • the title of the work: Implementing FFTs in Practice
  • the OpenStax-CNX URL where the work can be found: http://cnx.org/content/m16336/1.15/

See the citation section below for examples you can copy.

How to Cite and Attribute This Content

The following citation styles comply with the attribution requirements for the license (CC-BY 3.0) of this work:

American Chemical Society (ACS) Style Guide:

Johnson, S.; Frigo, M. Implementing FFTs in Practice, OpenStax-CNX Web site. http://cnx.org/content/m16336/1.15/, May 4, 2012.

American Medical Assocation (AMA) Manual of Style:

Johnson S, Frigo M. Implementing FFTs in Practice [OpenStax-CNX Web site]. May 4, 2012. Available at: http://cnx.org/content/m16336/1.15/.

American Psychological Assocation (APA) Publication Manual:

Johnson, S., & Frigo, M. (2012, May 4). Implementing FFTs in Practice. Retrieved from the OpenStax-CNX Web site: http://cnx.org/content/m16336/1.15/

Chicago Manual of Style (Bibliography):

Johnson, Steven, and Matteo Frigo. "Implementing FFTs in Practice." OpenStax-CNX. May 4, 2012. http://cnx.org/content/m16336/1.15/.

Chicago Manual of Style (Note):

Steven Johnson and Matteo Frigo, "Implementing FFTs in Practice," OpenStax-CNX, May 4, 2012, http://cnx.org/content/m16336/1.15/.

Chicago Manual of Style (Reference, in Author-Date style):

Johnson, S., & Frigo, M. 2012. Implementing FFTs in Practice. OpenStax-CNX, May 4, 2012. http://cnx.org/content/m16336/1.15/.

Modern Languages Association (MLA) Style Manual:

Johnson, Steven, and Matteo Frigo. Implementing FFTs in Practice. OpenStax-CNX. 4 May 2012 <http://cnx.org/content/m16336/1.15/>.