Bailey's FFT algorithm: Difference between revisions

Revision as of 15:42, 29 May 2023

Revision as of 15:47, 29 May 2023

Line 13:

The result (in natural order) is read column-by-column. Since the operations are performed column-wise and row-wise, step 2 and 4 (and reading the result) might include a [[matrix transpose]] to rearrange the elements in a way convenient for an FFT processing. The algorithm resembles a [[Multidimensional transform|2-dimensional FFT]], a 3-dimensional (and beyond) extensions are known as '''5-step FFT''', '''6-step FFT''', etc.{{sfn|Hart|Tornaría|Watkins|2010|p=191}}{{sfn|Na'mneh|Pan|2007|pp=191-192}}

The Bailey FFT is typically used for computing [[DFT]]s of large datasets, such as those used in scientific and engineering applications. The Bailey FFT is a very efficient algorithm, and it has been used to compute FFTs of datasets with billions{{fact}} of elements (when applied to the [[number-theoretic transform]], the datasets of the order of 10¹² elements were processed in mid-2000s{{sfn|Na'mneh|Pan|2007}}).

==References==