In-place self-sorting fast Fourier transform algorithm with local memory references Original Research Article

An new algorithm for the fast Fourier transform is proposed. Its three main characteristics are: being in-place (no auxiliary storage is required), being self-sorting or in-order (no bit reversal is necessary), and having locality of reference (items whose addresses are near one another are referenced closed together in time). A simple Fortran 90 program is given to illustrate the algorithm. In our platform, its performance is similar to the conventional algorithm for small transforms, and about three times faster for large transforms.