Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

Modified FFTs for fused multiply-add architectures


Authors: Elliot Linzer and Ephraim Feig
Journal: Math. Comp. 60 (1993), 347-361
MSC: Primary 65T20
MathSciNet review: 1159169
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 = {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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65T20

Retrieve articles in all journals with MSC: 65T20


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1993-1159169-0
PII: S 0025-5718(1993)1159169-0
Keywords: Fast Fourier transform, split-radix FFT, number of multiply-adds
Article copyright: © Copyright 1993 American Mathematical Society