Overview

To implement the Fourier transform directly, it is necessary to evaluate integrals involving highly oscillatory integrands. In rare cases this can be done analytically, such as for certain distributions or some rather simple functions. An exact analytical formula gives considerable insight into a problem, but the Fourier transform is far too useful to be restricted to just those few cases. In the more general case, we can employ a numerical integration method such as the extended Simpson' s rule ([2], p. 605ff), but the rapid oscillation of e ^ikx for large k will necessitate many small subintervals and much work. Also, Simpson's rule gives good approximations only when the function being transformed has four continuous derivatives.

Alternatively, we can approximate a function by samples and approximate the Fourier integral by the discrete Fourier transform or DFT. This approach requires applying a matrix whose order is the number of sample points. Since multiplying an N N matrix by a vector costs O( N ²) arithmetic operations, the problem scales rather badly as the number of sample points increases. However, if the samples are uniformly spaced, then the Fourier matrix can be factored into a product of just a few sparse matrices, and the resulting factors can be applied to a vector in a total of O( N log N) arithmetic operations. This is the so-called fast Fourier transform, or FFT.

FFT plays an enormous role in numerical...