A New Algorithm for Fast Generalized DFTs
A New Algorithm for Fast Generalized DFTs
复制标题
一种快速广义 DFT 的新算法
DOI：
10.1145/3301313
复制
发表时间：
2020
影响因子：
1.3
通讯作者：
Umans, Chris
中科院分区：
文献类型：
--
作者：
Hsu, Chloe Ching-Yun;Umans, Chris
本文给出了计算有限群G上广义离散傅里叶变换（DFT）的一种新算法.新算法使用O（<$G <$ω /2 +o（1））运算计算有限Lie型群上的广义DFT，包括线性、正交、辛族及其变体，以及所有有限Lie型单群.这里ω是矩阵乘法的指数，所以当ω = 2时，指数ω/2是最优的。以前，对超可解群、对称群和交错群都有“指数1”算法。即使在假设ω = 2的情况下，对于固定维数的线性群的族，也没有指数1算法是已知的，并且实际上，之前最著名的SL 2（Fq）算法具有指数4/3，尽管是重要工作的焦点。对于这个群，我们无条件地得到指数至多为1.19，当ω = 2时，指数为1.我们的算法还得到了计算一般有限群G上的广义DFT的改进指数，它超过了长期以来对任何ω的最佳上界.特别是，假设ω = 2，我们得到的指数是2，而之前的最佳值是3/2。
We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groupsG. The new algorithm usesO(∣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 groupsG, 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.
登录
查看更多内容
广义 FFTS - 对最近一些结果的调查 DAVID K. MASLEN 和 DANIEL N. ROCKMORE
DOI：
--
发表时间：
1999
期刊：
影响因子：
--
作者：
D. Rockmore
通讯作者：
D. Rockmore
广义FFT的一些应用
DOI：
10.1090/dimacs/028/19
发表时间：
1997
期刊：
Notes on the Brown-Douglas-Fillmore Theorem
影响因子：
--
作者：
D. Rockmore
通讯作者：
D. Rockmore
影响因子：
1.2
作者：
D. Maslen;D. Rockmore;Sarah Wolff
通讯作者：
Sarah Wolff
关于有限群的大子群
DOI：
--
发表时间：
1992
期刊：
影响因子：
--
作者：
A. Lev
通讯作者：
A. Lev
变量分离和有限群上傅里叶变换的计算，II
影响因子：
1.2
作者：
D. Maslen;D. Rockmore;Sarah Wolff
通讯作者：
Sarah Wolff