About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Mathematics of Computation
Paper
Modified ffts for fused multiply-add architectures
Abstract
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.