cannam@127:
cannam@127: FFTW 3 has semantics incompatible with earlier versions: its plans can
cannam@127: only be used for a given stride, multiplicity, and other
cannam@127: characteristics of the input and output arrays; these stronger
cannam@127: semantics are necessary for performance reasons. Thus, it is
cannam@127: impossible to efficiently emulate the older interface (whose plans can
cannam@127: be used for any transform of the same size). We believe that it
cannam@127: should be possible to upgrade most programs without any difficulty,
cannam@127: however.
cannam@127:
cannam@127:
cannam@127: There are several reasons:
cannam@127:
cannam@127:
It was important for performance reasons that the plan be specific to
cannam@127: array characteristics like the stride (and alignment, for SIMD), and
cannam@127: requiring that the user maintain these invariants is error prone.
cannam@127:
cannam@127:
In most high-performance applications, as far as we can tell, you are
cannam@127: usually transforming the same array over and over, so FFTW's semantics
cannam@127: should not be a burden.
cannam@127:
If you need to transform another array of the same size, creating a
cannam@127: new plan once the first exists is a cheap operation.
cannam@127:
cannam@127:
If you need to transform many arrays of the same size at once, you
cannam@127: should really use the plan_many routines in FFTW's "advanced"
cannam@127: interface.
cannam@127:
If the abovementioned array characteristics are the same, you are
cannam@127: willing to pay close attention to the documentation, and you really
cannam@127: need to, we provide a "new-array execution" interface to
cannam@127: apply a plan to a new array.
cannam@127:
cannam@127:
cannam@127: You are probably recreating the plan before every transform, rather
cannam@127: than creating it once and reusing it for all transforms of the same
cannam@127: size. FFTW is designed to be used in the following way:
cannam@127:
cannam@127:
cannam@127:
First, you create a plan. This will take several seconds.
cannam@127:
cannam@127:
Then, you reuse the plan many times to perform FFTs. These are fast.
cannam@127:
cannam@127:
cannam@127: If you don't need to compute many transforms and the time for the
cannam@127: planner is significant, you have two options. First, you can use the
cannam@127: FFTW_ESTIMATE option in the planner, which uses heuristics
cannam@127: instead of runtime measurements and produces a good plan in a short
cannam@127: time. Second, you can use the wisdom feature to precompute the plan;
cannam@127: see Q3.9 `Can I save FFTW's plans?'
cannam@127:
cannam@127:
cannam@127: Probably, NaNs or similar are creeping into your data, and the
cannam@127: slowdown is due to the resulting floating-point exceptions. For
cannam@127: example, be aware that repeatedly FFTing the same array is a diverging
cannam@127: process (because FFTW computes the unnormalized transform).
cannam@127:
cannam@127:
cannam@127:
cannam@127: Did the FFTW test programs pass (make check, or cd tests; make bigcheck if you want to be paranoid)? If so, you almost
cannam@127: certainly have a bug in your own code. For example, you could be
cannam@127: passing invalid arguments (such as wrongly-sized arrays) to FFTW, or
cannam@127: you could simply have memory corruption elsewhere in your program that
cannam@127: causes random crashes later on. Please don't complain to us unless
cannam@127: you can come up with a minimal self-contained program (preferably
cannam@127: under 30 lines) that illustrates the problem.
cannam@127:
cannam@127:
cannam@127:
cannam@127: As described in the manual, on 64-bit machines you must store the
cannam@127: plans in variables large enough to hold a pointer, for example
cannam@127: integer*8. We recommend using integer*8 on 32-bit machines as well, to simplify porting.
cannam@127:
cannam@127:
cannam@127:
cannam@127: People follow many different conventions for the DFT, and you should
cannam@127: be sure to know the ones that we use (described in the FFTW manual).
cannam@127: In particular, you should be aware that the
cannam@127: FFTW_FORWARD/FFTW_BACKWARD directions correspond to signs of -1/+1 in the exponent of the DFT definition.
cannam@127: (Numerical Recipes uses the opposite convention.)
cannam@127:
cannam@127: Finally, note that floating-point arithmetic is not exact, so
cannam@127: different FFT algorithms will give slightly different results (on the
cannam@127: order of the numerical accuracy; typically a fractional difference of
cannam@127: 1e-15 or so in double precision).
cannam@127:
cannam@127:
cannam@127: If you use FFTW_MEASURE or FFTW_PATIENT mode, then the algorithm FFTW employs is not deterministic: it depends on
cannam@127: runtime performance measurements. This will cause the results to vary
cannam@127: slightly from run to run. However, the differences should be slight,
cannam@127: on the order of the floating-point precision, and therefore should
cannam@127: have no practical impact on most applications.
cannam@127:
cannam@127:
cannam@127: If you use saved plans (wisdom) or FFTW_ESTIMATE mode, however, then the algorithm is deterministic and the results should be
cannam@127: identical between runs.
cannam@127:
cannam@127:
cannam@127: Yes. Starting with version 1.2, FFTW provides the
cannam@127: wisdom mechanism for saving plans; see the FFTW manual.
cannam@127:
cannam@127:
cannam@127:
cannam@127: Computing the forward transform followed by the backward transform (or
cannam@127: vice versa) yields the original array scaled by the size of the array.
cannam@127: (For multi-dimensional transforms, the size of the array is the
cannam@127: product of the dimensions.) We could, instead, have chosen a
cannam@127: normalization that would have returned the unscaled array. Or, to
cannam@127: accomodate the many conventions in this matter, the transform routines
cannam@127: could have accepted a "scale factor" parameter. We did not
cannam@127: do this, however, for two reasons. First, we didn't want to sacrifice
cannam@127: performance in the common case where the scale factor is 1. Second, in
cannam@127: real applications the FFT is followed or preceded by some computation
cannam@127: on the data, into which the scale factor can typically be absorbed at
cannam@127: little or no cost.
cannam@127:
cannam@127:
cannam@127: For human viewing of a spectrum, it is often convenient to put the
cannam@127: origin in frequency space at the center of the output array, rather
cannam@127: than in the zero-th element (the default in FFTW). If all of the
cannam@127: dimensions of your array are even, you can accomplish this by simply
cannam@127: multiplying each element of the input array by (-1)^(i + j + ...),
cannam@127: where i, j, etcetera are the indices of the element. (This trick is a
cannam@127: general property of the DFT, and is not specific to FFTW.)
cannam@127:
cannam@127:
cannam@127:
cannam@127: FFTW performs an FFT on an array of floating-point values. You can
cannam@127: certainly use it to compute the transform of an image or audio stream,
cannam@127: but you are responsible for figuring out your data format and
cannam@127: converting it to the form FFTW requires.
cannam@127:
cannam@127:
cannam@127:
cannam@127: The libraries must be listed in the correct order
cannam@127: (-lfftw3 -lm for FFTW 3.x) and after your program sources/objects. (The general rule is that if A uses B, then A must be listed before B in the link command.).
cannam@127:
cannam@127:
cannam@127: You're a C++ programmer, aren't you? You have to compile the FFTW
cannam@127: library and link it into your program, not just
cannam@127: #include <fftw3.h>. (Yes, this is really a FAQ.)
cannam@127:
cannam@127:
cannam@127: You cannot declare large arrays with automatic storage (e.g. via
cannam@127: fftw_complex array[N]); you should use fftw_malloc (or equivalent) to allocate the arrays you want
cannam@127: to transform if they are larger than a few hundred elements.
cannam@127:
cannam@127:
cannam@127:
cannam@127: After you create a plan, FFTW caches the information required to
cannam@127: quickly recreate the plan. (See Q3.9 `Can I save FFTW's plans?') It also maintains a small amount of other persistent memory. You can deallocate all of
cannam@127: FFTW's internally allocated memory, if you wish, by calling
cannam@127: fftw_cleanup(), as documented in the manual.
cannam@127:
cannam@127:
cannam@127: You should initialize your input array after creating the plan, unless you use FFTW_ESTIMATE: planning with FFTW_MEASURE or FFTW_PATIENT overwrites the input/output arrays, as described in the manual.
cannam@127:
cannam@127:
cannam@127:
cannam@127: Please do not ask us Windows-specific questions. We do not
cannam@127: use Windows. We know nothing about Visual Basic, Visual C++, or .NET.
cannam@127: Please find the appropriate Usenet discussion group and ask your
cannam@127: question there. See also Q2.2 `Does FFTW run on Windows?'.
cannam@127:
cannam@127:
cannam@127: In general, no, an FFT intrinsically computes all outputs from all
cannam@127: inputs. In principle, there is something called a
cannam@127: pruned FFT that can do what you want, but to compute K outputs out of N the
cannam@127: complexity is in general O(N log K) instead of O(N log N), thus saving
cannam@127: only a small additive factor in the log. (The same argument holds if
cannam@127: you instead have only K nonzero inputs.)
cannam@127:
cannam@127:
cannam@127: There are some specific cases in which you can get the O(N log K)
cannam@127: performance benefits easily, however, by combining a few ordinary
cannam@127: FFTs. In particular, the case where you want the first K outputs,
cannam@127: where K divides N, can be handled by performing N/K transforms of size
cannam@127: K and then summing the outputs multiplied by appropriate phase
cannam@127: factors. For more details, see pruned FFTs with FFTW.
cannam@127:
cannam@127: There are also some algorithms that compute pruned transforms
cannam@127: approximately, but they are beyond the scope of this FAQ.
cannam@127:
cannam@127:
cannam@127:
cannam@127: You can use the FFTW guru interface to create a rank-0 transform of
cannam@127: vector rank 2 where the vector strides are transposed. (A rank-0
cannam@127: transform is equivalent to a 1D transform of size 1, which. just
cannam@127: copies the input into the output.) Specifying the same location for
cannam@127: the input and output makes the transpose in-place.
cannam@127:
cannam@127:
cannam@127: For double-valued data stored in row-major format, plan creation looks
cannam@127: like this: