Multidimensional Cooley-Tukey algorithms revisited

DOI10.1006/AAMA.1996.0019MaRDI QIDQ675881zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 1 October 1997

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/aama.1996.0019

zbMATH Keywords

Cooley-Tukey algorithmdata flow patternsfast multidimensional Fourier transform algorithmsFFTfinite Abelian groupsGood-Thomas algorithmsnumerical examplerepresentation theory

Mathematics Subject Classification ID

Finite abelian groups (20K01) Numerical methods for discrete and fast Fourier transforms (65T50)

Review text

Based on the representation theory of finite Abelian groups, the authors derive fast multidimensional Fourier transform algorithms. For cyclic groups they obtain as special case the Cooley-Tukey and Good-Thomas algorithms. For groups with several generators they get a variety of multidimensional Cooley-Tukey type algorithms. They show that their approach results in data flow patterns which are different from the standard ``row-column approaches and demonstrate by a numerical example that in hierarchical memory environments these data flows are more efficient.

Recommendations

• The Fast Fourier Transform
• scientific article; zbMATH DE number 2177607
• The Cooley-Tukey FFT and group theory.
• scientific article; zbMATH DE number 3864463
• New algorithms for the multidimensional discrete Fourier transform

Cited in

(5)

• The fast Fourier transform and fast wavelet transform for patterns on the torus
• scientific article; zbMATH DE number 3864463 (Why is no real title available?)
• scientific article; zbMATH DE number 749495 (Why is no real title available?)
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Two-dimensional wreath product group-based image processing

This page was built for publication: Multidimensional Cooley-Tukey algorithms revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q675881)