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

DOI10.1007/S00041-016-9516-4zbMATH Open1384.43001arXiv1512.02445MaRDI QIDQ1704873FDOQ1704873

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)

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.

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

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

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)

Cites Work

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

Cited In (5)

• Computational bounds for doing harmonic analysis on permutation modules of finite groups
• Separation of variables and the computation of Fourier transforms on finite groups. II
• The efficient computation of Fourier transforms on semisimple algebras
• 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)