Double coset decompositions and computational harmonic analysis on groups
type: Item
instance of: scholarly article
title: Double coset decompositions and computational harmonic analysis on groups
zbMATH Open document ID: 0960.43006
DOI: 10.1007/BF02510144
author: David K. Maslen
author: Daniel N. Rockmore
published in: The Journal of Fourier Analysis and Applications
publication date: 2000-09-14T00:00:00Z
full work available at URL: https://eudml.org/doc/59648
review text: The paper describes a new technique for the efficient computation of a Fourier transform on a finite group. It utilizes the decomposition of a group into double cosets to derive algorithms that generalize the Cooley-Tukey FFT to arbitrary finite groups. The result is applied to the special linear group: Let \(q\) be an odd prime power. The Fourier transform of a complex valued function can be computed in no more than \(({1\over 2}q+3+16\log q)\cdot (q^3-q)\) scalar operations if a system of Gel'fand-Tsetlin bases for the irreducible representations of \(SL_2(F_q)\) are used.
Mathematics Subject Classification ID: 43A22
Mathematics Subject Classification ID: 20C15
Mathematics Subject Classification ID: 57T10
Mathematics Subject Classification ID: 65T50
zbMATH DE Number: 1508138
zbMATH Keywords: Fourier transform
zbMATH Keywords: finite group
zbMATH Keywords: Cooley-Tukey FFT
zbMATH Keywords: special linear group
zbMATH Keywords: Gel'fand-Tsetlin bases
zbMATH Keywords: irreducible representations
reviewed by: Karl-Heinz Zimmermann
MaRDI profile type: Publication
cites work: Is computing with the finite Fourier transform pure or applied mathematics?
cites work: Q4234180
cites work: Computing Irreducible Representations of Finite Groups
cites work: Existence and efficient construction of fast Fourier transforms on supersolvable groups
cites work: Computing Irreducible Representations of Supersolvable Groups
cites work: Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
cites work: Improved upper complexity bounds for the discrete Fourier transform
cites work: Inductive Limits of Finite Dimensional C ∗ -Algebras
cites work: Algebraic complexity theory. I: An introduction
cites work: Fast Fourier Transforms for Metabelian Groups
cites work: Fast generalized Fourier transforms
cites work: Q4298259
cites work: Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
cites work: An Algorithm for the Machine Calculation of Complex Fourier Series
cites work: Q4011207
cites work: A generalization of spectral analysis with application to ranked data
cites work: Q3995195
cites work: Average running time of the fast Fourier transform
cites work: Efficient Computation of the Fourier Transform on Finite Groups
cites work: Q4273603
cites work: Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs
cites work: Q3675490
cites work: Q4003957
cites work: Q4011821
cites work: Q5795544
cites work: Q3952291
cites work: Q4526979
cites work: Fast Fourier Analysis for SL2over a Finite Field and Related Numerical Experiments
cites work: The efficient computation of Fourier transforms on the symmetric group
cites work: Efficient computation of Fourier transforms on compact groups
cites work: Q4335301
cites work: Separation of variables and the computation of Fourier transforms on finite groups, I
cites work: Complex Representations of 𝐺𝐿(2,𝐾) for Finite Fields 𝐾
cites work: Q4335307
cites work: Fast Fourier transforms for wreath products
cites work: Fast Fourier analysis for abelian group extensions
cites work: Q4126536
cites work: Q5559954
cites work: On the algebraic structure of certain partially observable finite-state Markov processes
cites work: Q3883493
description: scientific article; zbMATH DE number 1508138