Separation of Variables and the Computation of Fourier Transforms on Finite Groups, II
Separation of Variables and the Computation of Fourier Transforms on Finite Groups, II
复制标题
变量分离和有限群上傅里叶变换的计算，II
DOI：
10.1007/s00041-016-9516-4
复制
发表时间：
2015
影响因子：
1.2
通讯作者：
Sarah Wolff
中科院分区：
文献类型：
--
作者：
D. Maslen;D. Rockmore;Sarah Wolff
我们提出了一种通用的图解方法来构造计算有限群上函数的傅里叶变换的有效算法。通过将Bratteli图与快速傅里叶变换算法的构造联系起来的工作进行扩展，我们明确地利用了路径代数与Gel 'fand-Tsetlin基的构造联系以及在颤振设置中的工作。我们将这个框架与由Bratteli图派生的构形空间的构造联系起来。在这种情况下，计算傅里叶变换的算法的复杂性降低为计算相关位形空间的维数。我们的方法给出了有限域上一般线性群、经典Weyl群和有限群的齐次空间的傅里叶变换计算的改进上界，同时也恢复了对称群的最著名算法。
We present a general diagrammatic approach to the construction of efficient algorithms for computing the Fourier transform of a function on a finite group. By extending work which connects Bratteli diagrams to the construction of Fast Fourier Transform algorithms we make explicit use of the path algebra connection to the construction of Gel’fand–Tsetlin bases and work in the setting of quivers. We relate this framework to the construction of a configuration space derived from a Bratteli diagram. In this setting the complexity of an algorithm for computing a Fourier transform reduces to the calculation of the dimension of the associated configuration space. Our methods give improved upper bounds for computing the Fourier transform for the general linear groups over finite fields, the classical Weyl groups, and homogeneous spaces of finite groups, while also recovering the best known algorithms for the symmetric group.