Jump to content

Bailey's FFT algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Dimawik (talk | contribs) at 20:11, 22 March 2023 (Dimawik moved page User:Dimawik/Bailey's FFT algorithm to User:Dimawik/Bailey FFT algorithm: more popular). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.