Efficient computation of Fourier inversion for finite groups

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient computation of Fourier inversion for finite groups

Full text

Pdf (1.91 MB)

Source

Journal of the ACM (JACM) archive
Volume 41 , Issue 1 (January 1994) table of contents

Pages: 31 - 66

Year of Publication: 1994

ISSN:0004-5411

Author

Daniel N. Rockmore

Harvard Univ., Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms review 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/174644.174646 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	~BABAI, L., AND R6NYAI, L. 1990. Computing irreducible representations of finite groups. Math. ~ Comp. 55, 705-722.
	3	Ulrich Baum , Michael Clausen, Some lower and upper complexity bounds for generalized Fourier transforms and their inverses, SIAM Journal on Computing, v.20 n.3, p.451-459, June 1991 [doi>10.1137/0220028]
	4	~BAUM, U., AND CLAUSEN, M. 1993. Fast Fourier transforms for symmetric groups: Theory and ~implementation. Math. Comp. 61, 833-848.
	5	~BETH, T. 1984. Vehrfahren der Schnellen Fourier-Transform. Teubner, Stuttgart, Germany.
	6	M. Clausen, Fast Fourier transforms for metabelian groups, SIAM Journal on Computing, v.18 n.3, p.584-593, June 1989 [doi>10.1137/0218040]
	7	Michael Clausen, Fast generalized Fourier transforms, Theoretical Computer Science, v.67 n.1, p.55-63, Sept. 1989 [doi>10.1016/0304-3975(89)90021-2]
	8	~CLAUSEN M., AND BAUM, U. 1993. Fast Fourier Transform. Wissenschaftsverlag, Manheim, ~Germany.
	9	~COLEMAN, A. J. 1966. Induced representations with applications to Sn and GL,,. Queen's Papers ~m Pure and Applied Mathematics, No. 4.
	10	D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
	11	~CURTIS, C., AND REINER, I. 1988. Representation Theory of Fimte Groups and Assoctative Algebras. ~ Wiley Classics Library. Wiley, New York.
	12	~DIACONIS, P. t980. Average running time of the fast Fourier transforms. J. Algorithms 1, ~187 208.
	13	~DIACONIS, P. 1988. Group Representations m Probabihty and Stattstlcs. Institute of Mathematical ~Statistics, Hayward, Calif.
	14	~DIACONIS, P. 1989. A generalization of spectral analysis with application to ranked data. Ann. ~Statistzcs 17, 949-979.
	15	~DIACONIS, P., AND ROCKMORE, D. 1990. Efficient computation of the Fourier transform on finite ~groups. J. AMS 3, 297-332.
	16	~DIXON, J. 1970. Computing irreducible representations of groups. Math. Comp. 24, 707 712.
	17	~DRISCOLL, J., AND HEALY, 1989. Asymtotically fast algorithms for spherical and related trans- ~forms. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Compuer Science. ~IEEE, New York, pp. 344-349.
	18	James R. Driscoll , Dennis M. Healy, Jr., Computing Fourier transforms and convolutions on the 2-sphere, Advances in Applied Mathematics, v.15 n.2, p.202-250, June 1994 [doi>10.1006/aama.1994.1008]
	19	James R. Driscoll , Dennis M. Healy , Daniel N. Rockmore, Fast Spherical Transforms on Distance Transitive Graphs, Dartmouth College, Hanover, NH, 1994
	20	~ELL1OTT, D., AND RAO, K. 1982. Fast Transforms, Academic Press, Orlando, Fla.
	21	Dennis M. Healy , Sean S. B. Moore , Daniel N. Rockmore, Efficiency and Stability Issues in the Numerical Computation of Fourier Transforms and Convolutions on the 2-Sphere, Dartmouth College, Hanover, NH, 1994
	22	~JAMES, G. D. 1978. The Representatzon Theory of the Symmetric Groups. In Lecture Notes in ~Mathematics, vol. 682. Springer-Verlag, Berlin.
	23	~JAMES, G. D., AND KERBER, h. 1981. The Representation Theory of the Symmetric Group. ~Addison-Wesley, Reading, Mass.
	24	~KEROV, S. g., AND VERSHIK, h. M. 1985. Asymptoties of the largest and the typical dimensions ~ of irreducible representations of the symmetric group. Func. Anal. AppI.. 21-31.
	25	David Keith Maslen, Fast transforms and sampling for compact groups, Harvard University, Cambridge, MA, 1993
	26	~MOORE, S., HEALY, D., AND ROCKMORE, D. 1993. Symmetry stabilization for polynomial evalua- ~tion and interpolation. LinearAlg. Appl. 192, 249-299.
	27	D. Rockmore, Computation of Fourier transforms on the symmetric group, Proceedings of the third conference on Computers and mathematics, p.156-165, May 1989, Boston, Massachusetts, United States
	28	Daniel Rockmore, Fast Fourier analysis for abelian group extensions, Advances in Applied Mathematics, v.11 n.2, p.164-204, Jun. 1990 [doi>10.1016/0196-8858(90)90008-M]

CITED BY

David K. Maslen , Daniel N. Rockmore, Adapted diameters and the efficient computation of Fourier transforms on finite groups, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.253-262, January 22-24, 1995, San Francisco, California, United States

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.1 Numerical Algorithms and Problems
Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.0 General
Subjects: Numerical algorithms
G.2 DISCRETE MATHEMATICS
G.2.1 Combinatorics
Subjects: Permutations and combinations
G.4 MATHEMATICAL SOFTWARE
Subjects: Algorithm design and analysis

J. Computer Applications
J.2 PHYSICAL SCIENCES AND ENGINEERING
Subjects: Mathematics and statistics

General Terms:
Algorithms, Theory

Keywords:
Fast Fourier Transform, Fourier inversion, finite groups, group convolution, group representations, symmetric group

REVIEW

"E. Feig : Reviewer"

Methods for the efficient computation of Fourier transforms on finite Abelian groups are well known, and indeed fast Fourier transform (FFT) algorithms are widely used. This research report presents extensions to general finite groups. Irreduc more...

Collaborative Colleagues:

Daniel N. Rockmore: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player