Separation of variables and the computation of Fourier transforms on finite groups. II

DOI10.1007/S00041-016-9516-4MaRDI QIDQ1704873zbMATH OpenFDO

Authors Daniel N. Rockmore, Sarah Wolff, David K. Maslen

Publication date 13 March 2018

Published in The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.02445

zbMATH Keywords

computational complexitygeneralized Fourier transformBratteli diagrampath algebra

Mathematics Subject Classification ID

Ordinary representations and characters (20C15) Fourier and Fourier-Stieltjes transforms on nonabelian groups and on semigroups, etc. (43A30) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: We present a general diagrammatic approach to the construction of efficient algorithms for computing the Fourier transform of a function on a finite group. By extending work which connects Bratteli diagrams to the construction of Fast Fourier Transform algorithms %cite{sovi}, we make explicit use of the path algebra connection to the construction of Gel'fand-Tsetlin bases and work in the setting of quivers. We relate this framework to the construction of a {em configuration space} derived from a Bratteli diagram. In this setting the complexity of an algorithm for computing a Fourier transform reduces to the calculation of the dimension of the associated configuration space. Our methods give improved upper bounds for computing the Fourier transform for the general linear groups over finite fields, the classical Weyl groups, and homogeneous spaces of finite groups, while also recovering the best known algorithms for the symmetric group and compact Lie groups.

Recommendations

• Separation of variables and the computation of Fourier transforms on finite groups. II
• Separation of variables and the computation of Fourier transforms on finite groups, I
• The efficient computation of Fourier transforms on the symmetric group
• Efficient Computation of the Fourier Transform on Finite Groups
• Efficient computation of Fourier inversion for finite groups

Cites work

• scientific article; zbMATH DE number 4160796 (Why is no real title available?)
• scientific article; zbMATH DE number 3896264 (Why is no real title available?)
• scientific article; zbMATH DE number 3771876 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 47598 (Why is no real title available?)
• scientific article; zbMATH DE number 53687 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 475357 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1004938 (Why is no real title available?)
• scientific article; zbMATH DE number 1004944 (Why is no real title available?)
• scientific article; zbMATH DE number 1111784 (Why is no real title available?)
• scientific article; zbMATH DE number 195200 (Why is no real title available?)
• scientific article; zbMATH DE number 910881 (Why is no real title available?)
• scientific article; zbMATH DE number 3056353 (Why is no real title available?)
• A Modified Split-Radix FFT With Fewer Arithmetic Operations
• A generalization of spectral analysis with application to ranked data
• A new matrix approach to real FFTs and convolutions of length \(2^k\)
• A ribbon Hopf algebra approach to the irreducible representations of centralizer algebras: The Brauer, Birman-Wenzl, and type A Iwahori-Hecke algebras
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Average running time of the fast Fourier transform
• Blind image deconvolution using a banded matrix method
• Classification of nuclear \(C^*\)-algebras. Entropy in operator algebras
• Computing Isotypic Projections with the Lanczos Iteration
• Differential Posets
• Double coset decompositions and computational harmonic analysis on groups
• Efficient Computation of the Fourier Transform on Finite Groups
• Fast generalized Fourier transforms
• Gauss and the history of the fast Fourier transform
• Inductive Limits of Finite Dimensional C ∗ -Algebras
• Is computing with the finite Fourier transform pure or applied mathematics?
• On the classification of inductive limits of sequences of semisimple finite-dimensional algebras
• Representations of the rook-Brauer algebra
• Seminormal Representations of Weyl Groups and Iwahori-Hecke Algebras
• Separation of variables and the computation of Fourier transforms on finite groups, I
• Separation of variables and the computation of Fourier transforms on finite groups. II
• The Cooley-Tukey FFT and group theory.
• The efficient computation of Fourier transforms on the symmetric group
• The quasi-partition algebra.
• The rook partition algebra
• Unzerlegbare Darstellungen. I. (Indecomposable representations. I)

Cited in

(5)

• Computational bounds for doing harmonic analysis on permutation modules of finite groups
• The efficient computation of Fourier transforms on semisimple algebras
• Separation of variables and the computation of Fourier transforms on finite groups. II
• On discrete groups of Euclidean isometries: representation theory, harmonic analysis and splitting properties
• Separation of variables and the computation of Fourier transforms on finite groups. II

This page was built for publication: Separation of variables and the computation of Fourier transforms on finite groups. II

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