Fast generalized DFTs for all finite groups

Chris Umans

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 an…