Optimality of the Fast Fourier transform

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimality of the Fast Fourier transform

Full text

Pdf (450 KB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 1 (January 1979) table of contents

Pages: 95 - 102

Year of Publication: 1979

ISSN:0004-5411

Author

Christos H. Papadimitriou

Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA and Harvard University, Cambridge, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 76, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322108.322118 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AGARWAL, R, AND BURRUS, C Fast convolution usmg Fermat number transforms IEEE Trans Acoust, Speech, Szgnal Processmg, A SSP-22, (1974), 87-97
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	Cocr~gAr,r, W T, ET AL What is the fast Fourier transform'~ IEEE Trans Audio and Electroacoust A U-15 (1967), 45-55
	4	COOLEY, j W, AND TOOKEY, J W An algorithm for the machine calculation of complex Fourier series Math Comput 199 (1965), 297-301
	5	MORGENSTERS, J Algonthmes hne~iires CR Acad Sct Par;s, Series A, 272 (April 19, 1971), 1058-1060
	6	Jacques Morgenstern, Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform, Journal of the ACM (JACM), v.20 n.2, p.305-306, April 1973 [doi>10.1145/321752.321761]
	7	Jacques Morgenstern, The Linear Complexity of Computation, Journal of the ACM (JACM), v.22 n.2, p.184-194, April 1975 [doi>10.1145/321879.321881]
	8	SCHONHAGE, A, AND STRASSEN, V Schnelle Multiplication grosser Zahlen Computing 7 (1971), 281-292
	9	WINOGRAD, S On computing the discrete Fourier transform Proc. Nat Acad Sct 73, 4 (1976), 1005-1006
	10	WINOGRAD, S On computing the discrete Fourier transform To appear in Math Comput