GNU Scientific Library Reference Manual - Third Edition (v1.12)by M. Galassi, J. Davies, J. Theiler, B. Gough, G. Jungman, P. Alken, M. Booth, F. Rossi Paperback (6"x9"), 592 pages, 60 figures ISBN 0954612078 RRP £24.95 ($39.95) |

## 15.1 Mathematical Definitions

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

ISBN 0954612078 | GNU Scientific Library Reference Manual - Third Edition (v1.12) | See the print edition |