A new algorithm for fast generalized DFTs

• Published in: arXiv.org 2018-03
• Main Authors: Hsu, Chloe Ching-Yun, Umans, Chris
• Format: Article
• Language: English
• Subjects: Algorithms; Fourier transforms; Multiplication; Upper bounds
• ISSN: 2331-8422

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 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\). 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 \(\omega = 2\)) for families of linear groups of fixed dimension, and indeed the previous best-known algorithm for \(SL_2(F_q)\) 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 \(\omega = 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 \(\omega\). In particular, assuming \(\omega = 2\), we achieve exponent \(\sqrt{2}\), while the previous best was \(3/2\).