Bailey's FFT algorithm
The Bailey FFT is a high-performance algorithm for computing the fast Fourier transform (FFT) on vector supercomputers. It is designed for systems with external or hierarchical memory, which are common in vector supercomputers. The Bailey FFT uses a number of techniques to reduce the number of passes through the data set, including:
- Strictly unit stride, long vector transfers between main memory and external storage
- A modest amount of scratch space in main memory
- Well-suited for vector and parallel computation
The Bailey FFT is typically used for computing DFTs of large datasets, such as those used in scientific and engineering applications.
Here is a brief overview of how the Bailey FFT works:
1. The data is first partitioned into groups of vectors. 2. Each group of vectors is then processed using a standard FFT algorithm. 3. The results of the individual FFTs are then combined to form the final FFT.
The Bailey FFT is a very efficient algorithm, and it has been used to compute FFTs of datasets with billions of elements.