Next: Overview of complex data FFTs, Up: Fast Fourier Transforms [Index]

Fast Fourier Transforms are efficient algorithms for calculating the discrete Fourier transform (DFT),

x_j = \sum_{k=0}^{n-1} z_k \exp(-2\pi i j k / n)

The DFT usually arises as an approximation to the continuous Fourier
transform when functions are sampled at discrete intervals in space or
time. The naive evaluation of the discrete Fourier transform is a
matrix-vector multiplication
*W\vec{z}*. A general matrix-vector multiplication takes
*O(n^2)* operations for *n* data-points. Fast Fourier
transform algorithms use a divide-and-conquer strategy to factorize the
matrix *W* into smaller sub-matrices, corresponding to the integer
factors of the length *n*. If *n* can be factorized into a
product of integers
*f_1 f_2 ... f_m* then the DFT can be computed in *O(n \sum
f_i)* operations. For a radix-2 FFT this gives an operation count of
*O(n \log_2 n)*.

All the FFT functions offer three types of transform: forwards, inverse
and backwards, based on the same mathematical definitions. The
definition of the *forward Fourier transform*,
*x = FFT(z)*, is,

x_j = \sum_{k=0}^{n-1} z_k \exp(-2\pi i j k / n)

and the definition of the *inverse Fourier transform*,
*x = IFFT(z)*, is,

z_j = {1 \over n} \sum_{k=0}^{n-1} x_k \exp(2\pi i j k / n).

The factor of *1/n* makes this a true inverse. For example, a call
to `gsl_fft_complex_forward`

followed by a call to
`gsl_fft_complex_inverse`

should return the original data (within
numerical errors).

In general there are two possible choices for the sign of the exponential in the transform/ inverse-transform pair. GSL follows the same convention as FFTPACK, using a negative exponential for the forward transform. The advantage of this convention is that the inverse transform recreates the original function with simple Fourier synthesis. Numerical Recipes uses the opposite convention, a positive exponential in the forward transform.

The *backwards FFT* is simply our terminology for an unscaled
version of the inverse FFT,

z^{backwards}_j = \sum_{k=0}^{n-1} x_k \exp(2\pi i j k / n).

When the overall scale of the result is unimportant it is often convenient to use the backwards FFT instead of the inverse to save unnecessary divisions.

Next: Overview of complex data FFTs, Up: Fast Fourier Transforms [Index]