Remote Access Mathematics of Computation
Green Open Access

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

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

Keywords: Fast Fourier transform, split-radix FFT, number of multiply-adds
Article copyright: © Copyright 1993 American Mathematical Society