A New Algorithm for Fast Generalized DFTs

摘要

We give an arithmetic algorithm using $O(|G|^{omega/2 + o(1)})$ operationsto compute the generalized Discrete Fourier Transform (DFT) over group $G$ forfinite groups of Lie type, including the linear, orthogonal, and symplecticfamilies 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$. Previously, "exponent one" algorithmswere known for supersolvable groups and the symmetric and alternating groups.No exponent one algorithms were known (even under the assumption $omega = 2$)for families of linear groups of fixed dimension, and indeed the previousbest-known algorithm for $SL_2(F_q)$ had exponent $4/3$ despite being the focusof significant effort. We unconditionally achieve exponent at most $1.19$ forthis group, and exponent one if $omega = 2$. We also show that $omega = 2$implies a $sqrt{2}$ exponent for general finite groups $G$, which beats thelongstanding previous best upper bound (assuming $omega = 2$) of $3/2$.