On the computational complexity of the general discrete fourier transform

AbstractIn this paper the complexity of computing the General Discrete Fourier Transform over group algebras of finite groups is studied. Starting with a short introduction to known results, the complexity gains of a new algorithm derived from Clifford's theorem are discussed. Applying these results to the class of finite solvable groups, new upper bounds, also for the complexity of the underlying group algebras, are derived