TABLE OF CONTENTS Fast Fourier Transform algorithms (FFT) for the computation of the Discrete Fourier Transform (DFT) is one of the most significant advances in computational methods. FFT is now an integral part in diverse fields of applications such as computation of physical and chemical systems based on first principles, global climate modelling, medical imaging, seismic modelling, telephony, computer graphics, to name a few. Most computational software for FFT consists of two kernel-type computations. The first kernel is usually called twiddle factor generation, which calculates a set of sine and cosine values. The second kernel is usually called a butterfly kernel. It calculates the composition of two linear operators. One is a short-length, p, DFT computation, and the other is a scaling by a set of roots of unity of the form [1 ?, ? 2, , ? p ?1] where ? = e ??? for some ?. Typically, a software package of FFT will have the butterfly kernels for various small number p, such as 2, 3, 4, 5, 7, 11.
It is rather common that within a certain application, FFT needs to be applied to a number of different data sets of the same size. As long as the data size remain fixed, the set of twiddle factors required is the same. Hence, most FFT software provides an initialization routine that computes and saves a set of twiddle factors.
Although it is common...
