Double coset decompositions and computational harmonic analysis on groups (Q1581065)

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.