annotate src/fftw-3.3.5/doc/FAQ/fftw-faq.html/section4.html @ 83:ae30d91d2ffe

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