A Caltech Library Service

A fast generalized DFT for finite groups of Lie type

Hsu, Chloe Ching-Yun and Umans, Chris (2018) A fast generalized DFT for finite groups of Lie type. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, pp. 1047-1059. ISBN 978-1-6119-7503-1.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We give an arithmetic algorithm using O(|G|^(ω/2+o(1))) operations to compute the generalized Discrete Fourier Transform (DFT) over group G for 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 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 ω = 2. We also show that ω = 2 implies a √2] exponent for general finite groups G, which beats the longstanding previous best upper bound (assuming ω = 2) of 3/2.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper ItemJournal Article
Hsu, Chloe Ching-Yun0000-0002-7743-3168
Alternate Title:A new algorithm for fast generalized DFTs
Additional Information:© 2018 SIAM. Supported by NSF grant CCF-1423544 and a Simons Foundation Investigator grant. We thank the SODA 2018 referees for their careful reading of this paper and many useful comments.
Funding AgencyGrant Number
Simons FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20180410-153010180
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:85736
Deposited By: Tony Diaz
Deposited On:11 Apr 2018 18:39
Last Modified:15 Nov 2019 17:46

Repository Staff Only: item control page