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