CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20180410-153010180

[img] PDF - Published Version
See Usage Policy.

640Kb
[img] PDF - Submitted Version
See Usage Policy.

267Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20180410-153010180

Abstract

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
https://dl.acm.org/citation.cfm?id=3175338PublisherArticle
https://arxiv.org/abs/1707.00349arXivDiscussion Paper
https://resolver.caltech.edu/CaltechAUTHORS:20191115-080137932Related ItemJournal Article
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSFCCF-1423544
Simons FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20180410-153010180
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20180410-153010180
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:85736
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:11 Apr 2018 18:39
Last Modified:15 Nov 2019 17:46

Repository Staff Only: item control page