Fast Fourier analysis for abelian group extensions (Q921894)

The Fourier transform FT of a complex-valued function f on a finite group G is defined as \(\hat f(\rho)=\sum_{s\in G}f(s)\rho(s)\) at an irreducible representation of G. Its inversion formula \(f(s)=(1/| G|)\sum_{\rho}d_{\rho}trace(\hat f(\rho)\rho(s^{-1}))\) determines f at all the irreducible representations of G. When G contains some nontrivial normal subgroup K such that \(G/K\) is abelian, the necessary number of arithmetic operations for the FT is reduced to \(O((| G| /| K|)T(K)+| G| \log (| G| /| K|))\), where \(T(K)\) is the necessary number of arithmetic operations for FT on K. Similar result is obtained for the inverse transform.