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 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?)

  • [1] L. Auslander, E. Feig, and S. Winograd, The multiplicative complexity of the discrete Fourier transform, Adv. in Appl. Math. 5 (1984), no. 1, 87–109. MR 736551, 10.1016/0196-8858(84)90005-8
  • [2] Richard E. Blahut, Fast algorithms for digital signal processing, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1985. MR 777867
  • [3] James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 0178586, 10.1090/S0025-5718-1965-0178586-1
  • [4] Pierre Duhamel, Implementation of “split-radix” FFT algorithms for complex, real, and real-symmetric data, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), no. 2, 285–295. MR 835552, 10.1109/TASSP.1986.1164811
  • [5] E. Feig, New algorithms for the 2-dimensional discrete Fourier transform, Technical Report RC8897, IBM Research, Yorktown Heights, NY, June 1981.
  • [6] M. T. Heideman and C. S. Burus, A bibliography of fast transform and convolution algorithms. II, Technical Report 8402, Rice Univ., Houston, TX, February 1984.
  • [7] E. Linzer and E. Feig, Implementation of efficient FFT algorithms on fused multiply/add architectures, Technical Report RC17330, IBM Research, Yorktown Heights, NY, 1990; IEEE Trans. Signal Process (to appear).
  • [8] -, New scaled DCT algorithms for fused multiply/add architectures, IEEE Internat. Conf. Accoust. Speech, Signal Process. (Toronto, Canada), IEEE, Piscataway, NJ, 1991, pp. 2201-2204.
  • [9] A. Mechentel, Private communication, 1990.
  • [10] R. K. Montoye, E. Hokenek, and S. L. Runyon, Design of the IBM RISC System/6000 floating point execution unit, IBM J. Res. Develop. 34 (1990), 71-77.
  • [11] Henri J. Nussbaumer and Philippe Quandalle, Fast computation of discrete Fourier transforms using polynomial transforms, IEEE Trans. Acoust. Speech Signal Process. 27 (1979), no. 2, 169–181. MR 523618, 10.1109/TASSP.1979.1163216
  • [12] C. M. Rader and N. M. Brenner, A new principle for fast Fourier transformation, IEEE Trans. Acoust. Speech Signal Process. 24 (1976), 264-265.
  • [13] G. E. Rivard, Direct fast Fourier transform of bivariate functions, IEEE Trans. Acoust. Speech Signal Process. 25 (1977), 250-252.
  • [14] H. V. Sorensen, M. T. Heideman, and C. S. Burus, On computing the split-radix FFT, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), 152-156.
  • [15] Richard Tolimieri, Myoung An, and Chao Lu, Algorithms for discrete Fourier transform and convolution, Springer-Verlag, New York, 1989. MR 1201161
  • [16] Martin Vetterli and Henri J. Nussbaumer, Simple FFT and DCT algorithms with reduced number of operations, Signal Process. 6 (1984), no. 4, 267–278 (English, with French and German summaries). MR 760430, 10.1016/0165-1684(84)90059-8
  • [17] Shmuel Winograd, On computing the discrete Fourier transform, Proc. Nat. Acad. Sci. U.S.A. 73 (1976), no. 4, 1005–1006. MR 0415993
  • [18] -, On computing the DFT, Math. Comp. 32 (1978), 175-199.
  • [19] S. Winograd, On the multiplicative complexity of the discrete Fourier transform, Adv. in Math. 32 (1979), no. 2, 83–117. MR 535617, 10.1016/0001-8708(79)90037-9

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