The efficient computation of Fourier transforms on the symmetric group |
| |
Authors: | David K Maslen |
| |
Institution: | Institut des Haute Études Scientifiques, Le Bois-Marie, 35 Route de Chartres, 91440, Bures-sur-Yvette, France |
| |
Abstract: | This paper introduces new techniques for the efficient computation of Fourier transforms on symmetric groups and their homogeneous spaces. We replace the matrix multiplications in Clausen's algorithm with sums indexed by combinatorial objects that generalize Young tableaux, and write the result in a form similar to Horner's rule. The algorithm we obtain computes the Fourier transform of a function on in no more than multiplications and the same number of additions. Analysis of our algorithm leads to several combinatorial problems that generalize path counting. We prove corresponding results for inverse transforms and transforms on homogeneous spaces. |
| |
Keywords: | |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
| 点击此处可从《Mathematics of Computation》下载免费的PDF全文 |
|