Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
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 = 2mwith8/3nm-16/9n+ 2/9(-1)mreal multiply-adds. For real input, this algorithm uses4/3nm– 17/9n+3-1/9(-1)mreal multiply-adds. We also describe efficient multidimensional FFTs. These algorithms can be used to compute the DFT of an nx n array of complex data using 14/3n2m- 4/3jn2(-1)m+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. © 1993 American Mathematical Society.
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
George Markowsky
J. Math. Anal. Appl.
Nimrod Megiddo
Journal of Symbolic Computation
T. Graham, A. Afzali, et al.
Microlithography 2000