annotate fft/fftw/fftw-3.3.4/doc/FAQ/fftw-faq.html/section4.html @ 40:223f770b5341 kissfft-double tip

Try a double-precision kissfft
author Chris Cannam
date Wed, 07 Sep 2016 10:40:32 +0100
parents 26056e866c29
children
rev   line source
Chris@19 1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
Chris@19 2 <html>
Chris@19 3 <head><title>
Chris@19 4 FFTW FAQ - Section 4
Chris@19 5 </title>
Chris@19 6 <link rev="made" href="mailto:fftw@fftw.org">
Chris@19 7 <link rel="Contents" href="index.html">
Chris@19 8 <link rel="Start" href="index.html">
Chris@19 9 <link rel="Next" href="section5.html"><link rel="Previous" href="section3.html"><link rel="Bookmark" title="FFTW FAQ" href="index.html">
Chris@19 10 </head><body text="#000000" bgcolor="#FFFFFF"><h1>
Chris@19 11 FFTW FAQ - Section 4 <br>
Chris@19 12 Internals of FFTW
Chris@19 13 </h1>
Chris@19 14
Chris@19 15 <ul>
Chris@19 16 <li><a href="#howworks" rel=subdocument>Q4.1. How does FFTW work?</a>
Chris@19 17 <li><a href="#whyfast" rel=subdocument>Q4.2. Why is FFTW so fast?</a>
Chris@19 18 </ul><hr>
Chris@19 19
Chris@19 20 <h2><A name="howworks">
Chris@19 21 Question 4.1. How does FFTW work?
Chris@19 22 </A></h2>
Chris@19 23
Chris@19 24 The innovation (if it can be so called) in FFTW consists in having a
Chris@19 25 variety of composable <i>solvers</i>, representing different FFT algorithms and implementation strategies, whose combination into a
Chris@19 26 particular <i>plan</i> for a given size can be determined at runtime according to the characteristics of your machine/compiler.
Chris@19 27 This peculiar software architecture allows FFTW to adapt itself to
Chris@19 28 almost any machine.
Chris@19 29 <p>
Chris@19 30 For more details (albeit somewhat outdated), see the paper &quot;FFTW:
Chris@19 31 An Adaptive Software Architecture for the FFT&quot;, by M. Frigo and
Chris@19 32 S. G. Johnson, <i>Proc. ICASSP</i> 3, 1381 (1998), also available at <A href="http://www.fftw.org">the FFTW web page</A>.
Chris@19 33 <h2><A name="whyfast">
Chris@19 34 Question 4.2. Why is FFTW so fast?
Chris@19 35 </A></h2>
Chris@19 36
Chris@19 37 This is a complex question, and there is no simple answer. In fact,
Chris@19 38 the authors do not fully know the answer, either. In addition to many
Chris@19 39 small performance hacks throughout FFTW, there are three general
Chris@19 40 reasons for FFTW's speed.
Chris@19 41 <ul>
Chris@19 42 <li> FFTW uses a variety of FFT algorithms and implementation styles
Chris@19 43 that can be arbitrarily composed to adapt itself to
Chris@19 44 a machine. See <A href="#howworks">Q4.1 `How does FFTW work?'</A>.
Chris@19 45 <li> FFTW uses a code generator to produce highly-optimized
Chris@19 46 routines for computing small transforms.
Chris@19 47
Chris@19 48 <li> FFTW uses explicit divide-and-conquer to take advantage
Chris@19 49 of the memory hierarchy.
Chris@19 50 </ul>
Chris@19 51 For more details (albeit somewhat outdated), see the paper &quot;FFTW:
Chris@19 52 An Adaptive Software Architecture for the FFT&quot;, by M. Frigo and
Chris@19 53 S. G. Johnson, <i>Proc. ICASSP</i> 3, 1381 (1998), available along with other references at
Chris@19 54 <A href="http://www.fftw.org">the FFTW web page</A>. <hr>
Chris@19 55 Next: <a href="section5.html" rel=precedes>Known bugs</a>.<br>
Chris@19 56 Back: <a href="section3.html" rev=precedes>Using FFTW</a>.<br>
Chris@19 57 <a href="index.html" rev=subdocument>Return to contents</a>.<p>
Chris@19 58 <address>
Chris@19 59 <A href="http://www.fftw.org">Matteo Frigo and Steven G. Johnson</A> / <A href="mailto:fftw@fftw.org">fftw@fftw.org</A>
Chris@19 60 - 04 March 2014
Chris@19 61 </address><br>
Chris@19 62 Extracted from FFTW Frequently Asked Questions with Answers,
Chris@19 63 Copyright &copy; 2014 Matteo Frigo and Massachusetts Institute of Technology.
Chris@19 64 </body></html>