A New Algorithm for Fast Generalized DFTs

摘要

We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups G. The new algorithm uses O(vertical bar G vertical bar(omega/2+o(1))) operations to compute the generalized DFT over finite groups of Lie type, including the linear, orthogonal, and symplectic families and their variants, as well as all finite simple groups of Lie type. Here omega is the exponent of matrix multiplication, so the exponent omega/2 is optimal if omega = 2.