Modified FFTs for Fused Multiply-Add Architectures
Elliot Linzer, Ephraim Feig · Mathematics of Computation · 1993
We introduce fast Fourier transform algorithms (FFTs) designed for fused multiply-add architectures. We show how to compute a complex discrete Fourier transform (DFT) of length $n = {2^m}$ with $\frac {8}{3}nm - \frac {{16}}{9}n + 2 - \frac {2}{9}{( - 1)^m}$ real multiply-adds. For real input, this algorithm uses $\frac {4}{3}nm - \frac {{17}}{9}n + 3 - \frac {1}{9}{( - 1)^m}$ real multiply-adds. We also describe efficient multidimensional FFTs. These algorithms can be used to compute the DFT of an $n \times n$ array of complex data using $\frac {{14}}{3}{n^2}m - \frac {4}{3}{n^2} - \frac {4}{9}n{( - 1)^m} + \frac {{16}}{9}$ real multiply-adds. For each problem studied, the number of multiply-adds that our algorithms use is a record upper bound for the number required.