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

PDF
- Published Version
See Usage Policy. 640Kb | |

PDF
- Submitted Version
See Usage Policy. 267Kb |

Use this Persistent URL to link to this item: http://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: |
| |||||||||

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: |
| |||||||||

Record Number: | CaltechAUTHORS:20180410-153010180 | |||||||||

Persistent URL: | http://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: | 11 Apr 2018 18:39 |

Repository Staff Only: item control page