Fast Fourier analysis for abelian group extensions

AbstractLet G be a finite group and f any complex-valued function defined on G and ϱ an irreducible complex matrix representation of G. The Fourier transform of | at ϱ is defined to be the matrix ΣJϵG|(s)ϱ(s). The Fourier transforms of | at all the irreducible representations of G determine | via the Fourier inversion formula |(s) = (1¦G¦)Σϱdϱ trace(\̂tf(ϱ)ϱ(s−1)). Direct computation of all Fourier transforms of | involves on the order of G2 operations as does direct computation of Fourier inversion. Here fast algorithms are obtained for both operations in the case in which G contains some nontrivial normal subgroup K such that GK is abelian. Consequently, fast algorithms for computing convolutions on G in this situation are also determined. Under the simplifying assumption of exponent for matrix multiplication equal to 2 (it is 2.38 as of this writing), it is shown that the number of operations needed to compute all Fourier transforms on G is O((¦G¦¦K¦)T(K) + ¦G¦log(¦G¦¦K¦)), where T(K) is the number of operations needed to compute Fourier transforms on K. An analogous result is obtained for Fourier inversion and more careful estimates made for arbitrary exponents of matrix multiplication. In particular, in the case in which G is metabelian (an abelian extension of an abelian subgroup) the assumptions hold and the first large class of noncommutative groups is obtained for which Fourier inversion and the computation of all Fourier transforms may be performed in O(¦G¦log(¦G¦)) operations