Fast generalized DFTs for all finite groups

Abstract

For any finite group $G$, we give an arithmetic algorithm to compute generalized Discrete Fourier Transforms (DFTs) with respect to $G$, using $O(|G{|}^{\omega /2+\epsilon })$ operations, for any $\epsilon >0$. Here, $\omega$ is the exponent of matrix multiplication.