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

  • [1] L. Auslander, E. Feig, and S. Winograd, The multiplicative complexity of the discrete Fourier transform, Adv. in Appl. Math. 5 (1984), 87-109. MR 736551 (86c:68037b)
  • [2] R. E. Blahut, Fast algorithms for digital signal processing, Addison-Wesley, Reading, MA, 1986. MR 777867 (86h:94005)
  • [3] J. W. Cooley and J. W. Tukey, An algorithm for the machine computation of complex Fourier series, Math. Comp. 19 (1965), 297-301. MR 0178586 (31:2843)
  • [4] P. Duhamel, Implementation of "split-radix" FFT algorithms for complex, real, and real-symmetric data, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), 285-295. MR 835552 (87e:94006)
  • [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] H. J. Nussbaumer, Fast computation of discrete Fourier transforms using polynomial transforms, IEEE Trans. Acoust. Speech Signal Process. 27 (1979), 169-181. MR 523618 (80c:94003)
  • [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] R. Tolimieri, M. An, and C. Lu, Algorithms for the discrete Fourier transform and convolution, Springer-Verlag, New York, 1989. MR 1201161 (93i:65131)
  • [16] M. Vetterli and H. J. Nussbaumer, Simple FFT and DCT algorithms with reduced number of operations, Signal Process. 6 (1984), 267-278. MR 760430 (85m:65128)
  • [17] S. Winograd, On computing the discrete Fourier transform, Proc. Nat. Acad. Sci. U.S.A. 73 (1976), 1005-1006. MR 0415993 (54:4070)
  • [18] -, On computing the DFT, Math. Comp. 32 (1978), 175-199.
  • [19] -, On the multiplicative complexity of the discrete Fourier transform, Adv. Math. 32 (1979), 83-117. MR 535617 (80e:68080)

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

American Mathematical Society