Journal article
Multidimensional Cooley–Tukey Algorithms Revisited
Advances in applied mathematics, v 17(4), pp 477-519
Dec 1996
Abstract
The representation theory of Abelian groups is used to obtain an algebraic divide-and-conquer algorithm for computing the finite Fourier transform. The algorithm computes the Fourier transform of a finite Abelian group in terms of the Fourier transforms of an arbitrary subgroup and its quotient. From this algebraic algorithm a procedure is derived for obtaining concrete factorizations of the Fourier transform matrix in terms of smaller Fourier transform matrices, diagonal multiplications, and permutations. For cyclic groups this gives as special cases the Cooley–Tukey and Good–Thomas algorithms. For groups with several generators, the procedure gives a variety of multidimensional Cooley–Tukey type algorithms. This method of designing multidimensional fast Fourier transform algorithms gives different data flow patterns from the standard “row–column” approaches. We present some experimental evidence that suggests that in hierarchical memory environments these data flows are more efficient.
Metrics
Details
- Title
- Multidimensional Cooley–Tukey Algorithms Revisited
- Creators
- L. Auslander - City University of New YorkJ.R. Johnson - Drexel UniversityR.W. Johnson - St. Cloud State University
- Publication Details
- Advances in applied mathematics, v 17(4), pp 477-519
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:A1996VZ33000004
- Scopus ID
- 2-s2.0-0030527049
- Other Identifier
- 991019169539304721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Mathematics, Applied