Modified FFTs for fused multiply-add architectures

Authors:
Elliot Linzer and Ephraim Feig

Journal:
Math. Comp. **60** (1993), 347-361

MSC:
Primary 65T20

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

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 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), 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)**

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