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 with real multiply-adds. For real input, this algorithm uses real multiply-adds. We also describe efficient multidimensional FFTs. These algorithms can be used to compute the DFT of an array of complex data using 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.

**[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

Retrieve articles in *Mathematics of Computation*
with MSC:
65T20

Retrieve articles in all journals with MSC: 65T20

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1993-1159169-0

Keywords:
Fast Fourier transform,
split-radix FFT,
number of multiply-adds

Article copyright:
© Copyright 1993
American Mathematical Society