A new algorithm for fast generalized DFTs

Chloe Ching-Yun Hsu, Chris Umans

We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups $G$. The new algorithm uses $O(|G{|}^{\omega /2+o(1)})$ operations to c…