Bailey's FFT algorithm: Difference between revisions

Revision as of 04:58, 7 August 2023

Revision as of 06:02, 17 August 2023

Line 12:

# Each row of a matrix is then independently processed using a standard FFT algorithm.

The result (in natural order) is read column-by-column. Since the operations are performed column-wise and row-wise, stepsteps 2 and 4 (and reading of 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|Al Na'mneh|Pan|2007|pp=191-192}}

The Bailey FFT is typically used for computing [[Discrete Fourier transform|DFTs]] 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 of elements (when applied to the [[number-theoretic transform]], the datasets of the order of 10¹² elements were processed in mid-2000s{{sfn|Al Na'mneh|Pan|2007}}).