📄 fftw_3.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"><HTML><HEAD><!-- This HTML file has been created by texi2html 1.52 from fftw.texi on 24 March 2003 --><TITLE>FFTW - FFTW Reference</TITLE></HEAD><BODY TEXT="#000000" BGCOLOR="#FFFFFF">Go to the <A HREF="fftw_1.html">first</A>, <A HREF="fftw_2.html">previous</A>, <A HREF="fftw_4.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>.<P><HR><P><H1><A NAME="SEC16">FFTW Reference</A></H1><P>This chapter provides a complete reference for all sequential (i.e.,one-processor) FFTW functions. We first define the data types uponwhich FFTW operates, that is, real, complex, and "halfcomplex" numbers(see Section <A HREF="fftw_3.html#SEC17">Data Types</A>). Then, in four sections, we explain the FFTWprogram interface for complex one-dimensional transforms(see Section <A HREF="fftw_3.html#SEC18">One-dimensional Transforms Reference</A>), complexmulti-dimensional transforms (see Section <A HREF="fftw_3.html#SEC24">Multi-dimensional Transforms Reference</A>), and real one-dimensional transforms (see Section <A HREF="fftw_3.html#SEC29">Real One-dimensional Transforms Reference</A>), real multi-dimensionaltransforms (see Section <A HREF="fftw_3.html#SEC34">Real Multi-dimensional Transforms Reference</A>).Section <A HREF="fftw_3.html#SEC41">Wisdom Reference</A> describes the <CODE>wisdom</CODE> mechanism forexporting and importing plans. Finally, Section <A HREF="fftw_3.html#SEC45">Memory Allocator Reference</A> describes how to change FFTW's default memory allocator.For parallel transforms, See Section <A HREF="fftw_4.html#SEC47">Parallel FFTW</A>.<H2><A NAME="SEC17">Data Types</A></H2><P><A NAME="IDX98"></A><A NAME="IDX99"></A><A NAME="IDX100"></A><P>The routines in the FFTW package use three main kinds of data types.<EM>Real</EM> and <EM>complex</EM> numbers should be already known to thereader. We also use the term <EM>halfcomplex</EM> to describe complexarrays in a special packed format used by the one-dimensional realtransforms (taking advantage of the <EM>hermitian</EM> symmetry that arisesin those cases).<P>By including <CODE><fftw.h></CODE> or <CODE><rfftw.h></CODE>, you will have accessto the following definitions:<PRE>typedef double fftw_real;typedef struct { fftw_real re, im;} fftw_complex;#define c_re(c) ((c).re)#define c_im(c) ((c).im)</PRE><P><A NAME="IDX101"></A><A NAME="IDX102"></A><P>All FFTW operations are performed on the <CODE>fftw_real</CODE> and<CODE>fftw_complex</CODE> data types. For <CODE>fftw_complex</CODE> numbers, thetwo macros <CODE>c_re</CODE> and <CODE>c_im</CODE> retrieve, respectively, the realand imaginary parts of the number.<P>A <EM>real array</EM> is an array of real numbers. A <EM>complex array</EM>is an array of complex numbers. A one-dimensional array X ofn complex numbers is <EM>hermitian</EM> if the following propertyholds:for all 0 <= i < n, we have X<sub>i</sub> = conj(X<sub>n-i</sub>)}.Hermitian arrays are relevant to FFTW because the Fourier transform of areal array is hermitian.<P>Because of its symmetry, a hermitian array can be stored in half thespace of a complex array of the same size. FFTW's one-dimensional realtransforms store hermitian arrays as <EM>halfcomplex</EM> arrays. Ahalfcomplex array of size n is<A NAME="IDX103"></A>a one-dimensional array of n <CODE>fftw_real</CODE> numbers. Ahermitian array X in stored into a halfcomplex array Y asfollows.For all integers i such that 0 <= i <= n / 2, we haveY<sub>i</sub> = Re(X<sub>i</sub>). For all integers i such that 0< i < n / 2, we have Y<sub>n-i</sub> = Im(X<sub>i</sub>).<P>We now illustrate halfcomplex storage for n = 4 and n = 5,since the scheme depends on the parity of n. Let n = 4.In this case, we haveY<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),Y<sub>2</sub> = Re(X<sub>2</sub>), and Y<sub>3</sub> = Im(X<sub>1</sub>).Let now n = 5. In this case, we haveY<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),Y<sub>2</sub> = Re(X<sub>2</sub>), Y<sub>3</sub> = Im(X<sub>2</sub>),and Y<sub>4</sub> = Im(X<sub>1</sub>).<P><A NAME="IDX104"></A>By default, the type <CODE>fftw_real</CODE> equals the C type <CODE>double</CODE>.To work in single precision rather than double precision, <CODE>#define</CODE>the symbol <CODE>FFTW_ENABLE_FLOAT</CODE> in <CODE>fftw.h</CODE> and then recompilethe library. On Unix systems, you can instead use <CODE>configure--enable-float</CODE> at installation time (see Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>).<A NAME="IDX105"></A><A NAME="IDX106"></A><P>In version 1 of FFTW, the data types were called <CODE>FFTW_REAL</CODE> and<CODE>FFTW_COMPLEX</CODE>. We changed the capitalization for consistency withthe rest of FFTW's conventions. The old names are still supported, buttheir use is deprecated.<A NAME="IDX107"></A><A NAME="IDX108"></A><H2><A NAME="SEC18">One-dimensional Transforms Reference</A></H2><P>The one-dimensional complex routines are generally prefixed with<CODE>fftw_</CODE>. Programs using FFTW should be linked with <CODE>-lfftw-lm</CODE> on Unix systems, or with the FFTW and standard math libraries ingeneral.<H3><A NAME="SEC19">Plan Creation for One-dimensional Transforms</A></H3><PRE>#include <fftw.h>fftw_plan fftw_create_plan(int n, fftw_direction dir, int flags);fftw_plan fftw_create_plan_specific(int n, fftw_direction dir, int flags, fftw_complex *in, int istride, fftw_complex *out, int ostride);</PRE><P><A NAME="IDX109"></A><A NAME="IDX110"></A><A NAME="IDX111"></A><A NAME="IDX112"></A><P>The function <CODE>fftw_create_plan</CODE> creates a plan, which isa data structure containing all the information that <CODE>fftw</CODE>needs in order to compute the 1D Fourier transform. You cancreate as many plans as you need, but only one plan for a givenarray size is required (a plan can be reused many times).<P><CODE>fftw_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE>if, for some reason, the plan can't be created. In thedefault installation, this cannot happen, but it is possibleto configure FFTW in such a way that some input sizes areforbidden, and FFTW cannot create a plan.<P>The <CODE>fftw_create_plan_specific</CODE> variant takes as additionalarguments specific input/output arrays and their strides. For the lastfour arguments, you should pass the arrays and strides that you willeventually be passing to <CODE>fftw</CODE>. The resulting plans will beoptimized for those arrays and strides, although they may be used onother arrays as well. Note: the contents of the in and out arrays are<EM>destroyed</EM> by the specific planner (the initial contents areignored, so the arrays need not have been initialized).<H4>Arguments</H4><UL><LI><CODE>n</CODE> is the size of the transform. It can be any positive integer. <UL><LI>FFTW is best at handling sizes of the form2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP> 11<SUP>e</SUP> 13<SUP>f</SUP>,where e+f is either 0 or1, and the other exponents are arbitrary. Other sizes arecomputed by means of a slow, general-purpose routine (which neverthelessretains O(n lg n)performance, even for prime sizes). (It ispossible to customize FFTW for different array sizes.See Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>, for more information.) Transformswhose sizes are powers of 2 are especially fast.</UL><LI><CODE>dir</CODE> is the sign of the exponent in the formula thatdefines the Fourier transform. It can be -1 or +1.The aliases <CODE>FFTW_FORWARD</CODE> and <CODE>FFTW_BACKWARD</CODE>are provided, where <CODE>FFTW_FORWARD</CODE> stands for -1.<LI><A NAME="IDX113"></A><CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following:<UL><LI><CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan byactually <EM>computing</EM> several FFTs and measuring theirexecution time. Depending on the installation, this can take sometime. <A NAME="DOCF2" HREF="fftw_foot.html#FOOT2">(2)</A><LI><CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"plan (for a RISC processor with many registers). If neither<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is<CODE>FFTW_ESTIMATE</CODE>.<LI><CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input andoutput arrays will be distinct (this is the default).<A NAME="IDX114"></A><LI><A NAME="IDX115"></A><CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want the outputin the input array. The algorithm used is not necessarily in place:FFTW is able to compute true in-place transforms only for small valuesof <CODE>n</CODE>. If FFTW is not able to compute the transform in-place, itwill allocate a temporary array (unless you provide one yourself),compute the transform out of place, and copy the result back.<EM>Warning: This option changes the meaning of some parameters of<CODE>fftw</CODE></EM> (see Section <A HREF="fftw_3.html#SEC21">Computing the One-dimensional Transform</A>).The in-place option is mainly provided for people who want to writetheir own in-place multi-dimensional Fourier transform, using FFTW as abase. For example, consider a three-dimensional <CODE>n * n * n</CODE>transform. An out-of-place algorithm will need another array (which maybe huge). However, FFTW can compute the in-place transform alongeach dimension using only a temporary array of size <CODE>n</CODE>.Moreover, if FFTW happens to be able to compute the transform trulyin-place, no temporary array and no copying are needed. As distributed,FFTW `knows' how to compute in-place transforms of size 1, 2, 3, 4, 5, 6,7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32 and 64.The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.<LI><A NAME="IDX116"></A><CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to helpin the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)This can greatly speed the creation of plans, especially with the<CODE>FFTW_MEASURE</CODE> option. <CODE>FFTW_ESTIMATE</CODE> plans can also takeadvantage of <CODE>wisdom</CODE> to produce a more optimal plan (based on pastmeasurements) than the estimation heuristic would normallygenerate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>will also be generated if the current transform size is not completelyunderstood by existing <CODE>wisdom</CODE>.</UL><LI><CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for<CODE>fftw_create_plan_specific</CODE>): see corresponding arguments in thedescription of <CODE>fftw</CODE>. (See Section <A HREF="fftw_3.html#SEC21">Computing the One-dimensional Transform</A>.) In particular, the <CODE>out</CODE> and <CODE>ostride</CODE>parameters have the same special meaning for <CODE>FFTW_IN_PLACE</CODE>transforms as they have for <CODE>fftw</CODE>.</UL><H3><A NAME="SEC20">Discussion on Specific Plans</A></H3><P><A NAME="IDX117"></A>We recommend the use of the specific planners, even in cases where youwill be transforming arrays different from those passed to the specificplanners, as they confer the following advantages:<UL><LI>The resulting plans will be optimized for your specific arrays andstrides. This may or may not make a significant difference, but itcertainly doesn't hurt. (The ordinary planner does its planning basedupon a stride-one temporary array that it allocates.)<LI>Less intermediate storage is required during the planning process. (Theordinary planner uses O(<CODE>N</CODE>) temporary storage, where <CODE>N</CODE> isthe maximum dimension, while it is creating the plan.)<LI>For multi-dimensional transforms, new parameters become accessible foroptimization by the planner. (Since multi-dimensional arrays can bevery large, we don't dare to allocate one in the ordinary planner forexperimentation. This prevents us from doing certain optimizationsthat can yield dramatic improvements in some cases.)</UL><P>On the other hand, note that <EM>the specific planner destroys thecontents of the <CODE>in</CODE> and <CODE>out</CODE> arrays</EM>.<H3><A NAME="SEC21">Computing the One-dimensional Transform</A></H3><PRE>#include <fftw.h>void fftw(fftw_plan plan, int howmany, fftw_complex *in, int istride, int idist, fftw_complex *out, int ostride, int odist);void fftw_one(fftw_plan plan, fftw_complex *in, fftw_complex *out);</PRE><P><A NAME="IDX118"></A><A NAME="IDX119"></A>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -