Modified FFTs for fused multiplyadd architectures
Authors:
Elliot Linzer and Ephraim Feig
Journal:
Math. Comp. 60 (1993), 347361
MSC:
Primary 65T20
MathSciNet review:
1159169
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We introduce fast Fourier transform algorithms (FFTs) designed for fused multiplyadd architectures. We show how to compute a complex discrete Fourier transform (DFT) of length with real multiplyadds. For real input, this algorithm uses real multiplyadds. We also describe efficient multidimensional FFTs. These algorithms can be used to compute the DFT of an array of complex data using real multiplyadds. For each problem studied, the number of multiplyadds 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 (86c:68037b), http://dx.doi.org/10.1016/01968858(84)900058
 [2]
Richard
E. Blahut, Fast algorithms for digital signal processing,
AddisonWesley Publishing Company Advanced Book Program, Reading, MA, 1985.
MR 777867
(86h:94005)
 [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
(31 #2843), http://dx.doi.org/10.1090/S00255718196501785861
 [4]
Pierre
Duhamel, Implementation of “splitradix” FFT algorithms
for complex, real, and realsymmetric data, IEEE Trans. Acoust. Speech
Signal Process. 34 (1986), no. 2, 285–295. MR 835552
(87e:94006), http://dx.doi.org/10.1109/TASSP.1986.1164811
 [5]
E. Feig, New algorithms for the 2dimensional 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. 22012204.
 [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), 7177.
 [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
(80c:94003), http://dx.doi.org/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), 264265.
 [13]
G. E. Rivard, Direct fast Fourier transform of bivariate functions, IEEE Trans. Acoust. Speech Signal Process. 25 (1977), 250252.
 [14]
H. V. Sorensen, M. T. Heideman, and C. S. Burus, On computing the splitradix FFT, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), 152156.
 [15]
Richard
Tolimieri, Myoung
An, and Chao
Lu, Algorithms for discrete Fourier transform and convolution,
SpringerVerlag, New York, 1989. MR 1201161
(93i:65131)
 [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
(85m:65128), http://dx.doi.org/10.1016/01651684(84)900598
 [17]
Shmuel
Winograd, On computing the discrete Fourier transform, Proc.
Nat. Acad. Sci. U.S.A. 73 (1976), no. 4,
1005–1006. MR 0415993
(54 #4070)
 [18]
, On computing the DFT, Math. Comp. 32 (1978), 175199.
 [19]
S.
Winograd, On the multiplicative complexity of the discrete Fourier
transform, Adv. in Math. 32 (1979), no. 2,
83–117. MR
535617 (80e:68080), http://dx.doi.org/10.1016/00018708(79)900379
 [1]
 L. Auslander, E. Feig, and S. Winograd, The multiplicative complexity of the discrete Fourier transform, Adv. in Appl. Math. 5 (1984), 87109. MR 736551 (86c:68037b)
 [2]
 R. E. Blahut, Fast algorithms for digital signal processing, AddisonWesley, 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), 297301. MR 0178586 (31:2843)
 [4]
 P. Duhamel, Implementation of "splitradix" FFT algorithms for complex, real, and realsymmetric data, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), 285295. MR 835552 (87e:94006)
 [5]
 E. Feig, New algorithms for the 2dimensional 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. 22012204.
 [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), 7177.
 [11]
 H. J. Nussbaumer, Fast computation of discrete Fourier transforms using polynomial transforms, IEEE Trans. Acoust. Speech Signal Process. 27 (1979), 169181. 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), 264265.
 [13]
 G. E. Rivard, Direct fast Fourier transform of bivariate functions, IEEE Trans. Acoust. Speech Signal Process. 25 (1977), 250252.
 [14]
 H. V. Sorensen, M. T. Heideman, and C. S. Burus, On computing the splitradix FFT, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), 152156.
 [15]
 R. Tolimieri, M. An, and C. Lu, Algorithms for the discrete Fourier transform and convolution, SpringerVerlag, 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), 267278. MR 760430 (85m:65128)
 [17]
 S. Winograd, On computing the discrete Fourier transform, Proc. Nat. Acad. Sci. U.S.A. 73 (1976), 10051006. MR 0415993 (54:4070)
 [18]
 , On computing the DFT, Math. Comp. 32 (1978), 175199.
 [19]
 , On the multiplicative complexity of the discrete Fourier transform, Adv. Math. 32 (1979), 83117. 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
DOI:
http://dx.doi.org/10.1090/S00255718199311591690
PII:
S 00255718(1993)11591690
Keywords:
Fast Fourier transform,
splitradix FFT,
number of multiplyadds
Article copyright:
© Copyright 1993 American Mathematical Society
