Efficient Computation of the Fourier Transform on Finite Groups

DOI10.2307/1990955zbMath0709.65125OpenAlexW4253674326MaRDI QIDQ3493168

Daniel N. Rockmore, Persi Diaconis

Publication date: 1990

Full work available at URL: https://doi.org/10.2307/1990955

zbMATH Keywords

Fourier transformirreducible representationfast algorithmssymmetric groupfinite groupinverse transformmatrix multiplicationblock diagonal formDirect computation

Mathematics Subject Classification ID

Ordinary representations and characters (20C15) Numerical methods for discrete and fast Fourier transforms (65T50) Representations of groups, semigroups, etc. (aspects of abstract harmonic analysis) (43A65) Numerical solutions to equations with linear operators (65J10)

Related Items

Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments, Quantum Fourier transform over symmetric groups -- improved result, Quantum mechanics on finite groups, Generating fast Fourier transforms of solvable groups, Operator calculus approach to orthogonal polynomial expansions, Separation of variables and the computation of Fourier transforms on finite groups. II, Sampling theorem and discrete Fourier transform on the Riemann sphere, Bentness and nonlinearity of functions on finite groups, Fast Fourier Transforms for Symmetric Groups: Theory and Implementation, The efficient computation of Fourier transforms on the symmetric group, Applications of the generalized Fourier transform in numerical linear algebra, Fast Fourier transforms for the rook monoid, Fast Fourier transforms for finite inverse semigroups, The efficient computation of Fourier transforms on semisimple algebras, Unnamed Item, Quantum algorithms for algebraic problems, Transition matrices between Young's natural and seminormal representations, Efficient computation of Fourier transforms on compact groups, Harmonic analysis on \(SL(2,\mathbb{C})\) and projectively adapted pattern representation, Double coset decompositions and computational harmonic analysis on groups, Fourier transforms with respect to monomial representations, Improved upper complexity bounds for the discrete Fourier transform, Decomposing monomial representations of solvable groups.

Cites Work

• Maximal degrees for Young diagrams in a strip
• Matrix multiplication via arithmetic progressions
• Fast Fourier analysis for abelian group extensions
• The Radon transform on \({\mathbb{Z}}^ k_ 2\)
• Asymptotics of maximal and typical dimensions of irreducible representations of a symmetric group
• On the computational complexity of the general discrete Fourier transform
• Relations between Young's natural and the Kazhdan-Lusztig representations of \(S_ n\)
• Fast generalized Fourier transforms
• A variational problem for random Young tableaux
• The complexity of group algebra computations
• The representation theory of the symmetric groups
• A generalization of spectral analysis with application to ranked data
• Asymptotic values for degrees associated with strips of Young diagrams
• A combinatorial problem in the symmetric group
• Representations of permutation groups. Part I
• Analogues of Poisson's Summation Formula
• On the length of subgroup chains in the symmetric group
• On the Zeros of the Askey–Wilson Polynomials, with Applications to Coding Theory
• Fast Fourier Transforms for Metabelian Groups
• Average running time of the fast Fourier transform
• Is computing with the finite Fourier transform pure or applied mathematics?
• Generating a random permutation with random transpositions
• On Computing the Discrete Fourier Transform
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item