skip to main content

Theory Group Meeting

Tuesday, June 5, 2018
4:00pm to 5:00pm
Add to Cal
Annenberg 322
A new algorithm for fast generalized DFTs
Chris Umans, Caltech,

ABSTRACT:  We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups G. The new algorithm uses O(|G|ω/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 ω is the exponent of matrix multiplication, so the exponent ω/2 is optimal if ω=2. Previously, "exponent one" algorithms were known for supersolvable groups and the symmetric and alternating groups. No exponent one algorithms were known (even under the assumption ω=2) for families of linear groups of fixed dimension, and indeed the previous best-known algorithm for SL2(Fq) had exponent 4/3 despite being the focus of significant effort. We unconditionally achieve exponent at most 1.19 for this group, and exponent one if ω=2.
Our algorithm also yields an improved exponent for computing the generalized DFT over general finite groups G, which beats the longstanding previous best upper bound, for any ω. In particular, assuming ω=2, we achieve exponent 2–√, while the previous best was 3/2.

Joint work with Chloe Ching-Yun Hsu

For more information, please contact Bonnie Leung by email at [email protected].