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> |