Geodesic
Efficient computation of the Fourier transform on finite groups
Journal of the American Mathematical Society, Tome 03 (1990) no. 2, pp. 297-332

Voir la notice de l'article provenant de la source American Mathematical Society

Let $G$ be a finite group, $f:G \to {\mathbf {C}}$ a function, and $\rho$ an irreducible representation of $G$. The Fourier transform is defined as $\hat f(\rho ) = {\Sigma _{s \in G}}f(s)\rho (s)$. Direct computation for all irreducible representations involves order ${\left | G \right |^2}$ operations. We derive fast algorithms and develop them for the symmetric group ${S_n}$. There, ${(n!)^2}$ is reduced to $n{(n!)^{a/2}}$, where $a$ is the constant for matrix multiplication (2.38 as of this writing). Variations of the algorithm allow efficient computation for “small” representations. A practical version of the algorithm is given on ${S_n}$. Numerical evidence is presented to show a speedup by a factor of 100 for $n = 9$. 
@article{10_1090_S0894_0347_1990_1030655_4,
     author = {Diaconis, Persi and Rockmore, Daniel},
     title = {Efficient computation of the {Fourier} transform on finite groups},
     journal = {Journal of the American Mathematical Society},
     pages = {297--332},
     publisher = {mathdoc},
     volume = {03},
     number = {2},
     year = {1990},
     doi = {10.1090/S0894-0347-1990-1030655-4},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1990-1030655-4/}
}
TY  - JOUR
AU  - Diaconis, Persi
AU  - Rockmore, Daniel
TI  - Efficient computation of the Fourier transform on finite groups
JO  - Journal of the American Mathematical Society
PY  - 1990
SP  - 297
EP  - 332
VL  - 03
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1990-1030655-4/
DO  - 10.1090/S0894-0347-1990-1030655-4
ID  - 10_1090_S0894_0347_1990_1030655_4
ER  - 
%0 Journal Article
%A Diaconis, Persi
%A Rockmore, Daniel
%T Efficient computation of the Fourier transform on finite groups
%J Journal of the American Mathematical Society
%D 1990
%P 297-332
%V 03
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1990-1030655-4/
%R 10.1090/S0894-0347-1990-1030655-4
%F 10_1090_S0894_0347_1990_1030655_4
Diaconis, Persi; Rockmore, Daniel. Efficient computation of the Fourier transform on finite groups. Journal of the American Mathematical Society, Tome 03 (1990) no. 2, pp. 297-332. doi: 10.1090/S0894-0347-1990-1030655-4

[1] Aho, Alfred V., Hopcroft, John E., Ullman, Jeffrey D. The design and analysis of computer algorithms 1975

[2] Askey, Richard, Regev, Amitai Maximal degrees for Young diagrams in a strip European J. Combin. 1984 189 191

[3] Atkinson, M. D. The complexity of group algebra computations Theoret. Comput. Sci. 1977/78 205 209

[4] Auslander, L., Tolimieri, R. Is computing with the finite Fourier transform pure or applied mathematics? Bull. Amer. Math. Soc. (N.S.) 1979 847 897

[5] Babai, Lã¡Szlã³ On the length of subgroup chains in the symmetric group Comm. Algebra 1986 1729 1736

[6] Beth, Thomas Verfahren der schnellen Fourier-Transformation 1984 316

[7] Beth, Thomas On the computational complexity of the general discrete Fourier transform Theoret. Comput. Sci. 1987 331 339

[8] Chihara, Laura On the zeros of the Askey-Wilson polynomials, with applications to coding theory SIAM J. Math. Anal. 1987 191 207

[9] Clausen, Michael Fast Fourier transforms for metabelian groups SIAM J. Comput. 1989 584 593

[10] Clausen, Michael Fast generalized Fourier transforms Theoret. Comput. Sci. 1989 55 63

[11] Coleman, A. J. Induced representations with applications to 𝑆_{𝑛} and 𝐺𝐿(𝑛) 1966

[12] Cooley, James W., Tukey, John W. An algorithm for the machine calculation of complex Fourier series Math. Comp. 1965 297 301

[13] Diaconis, Persi Average running time of the fast Fourier transform J. Algorithms 1980 187 208

[14] Diaconis, Persi A generalization of spectral analysis with application to ranked data Ann. Statist. 1989 949 979

[15] Diaconis, Persi Group representations in probability and statistics 1988

[16] Diaconis, Persi, Graham, R. L. The Radon transform on 𝑍^{𝑘}₂ Pacific J. Math. 1985 323 345

[17] Diaconis, Persi, Shahshahani, Mehrdad Generating a random permutation with random transpositions Z. Wahrsch. Verw. Gebiete 1981 159 179

[18] Elliott, Douglas F., Rao, K. Ramamohan Fast transforms 1982

[19] Goldstine, Herman H. A history of numerical analysis from the 16th through the 19th century 1977

[20] Good, I. J. The interaction algorithm and practical Fourier analysis J. Roy. Statist. Soc. Ser. B 1958 361 372

[21] Good, I. J. Analogues of Poisson’s summation formula Amer. Math. Monthly 1962 259 266

[22] James, G. D. The representation theory of the symmetric groups 1978

[23] James, Gordon, Kerber, Adalbert The representation theory of the symmetric group 1981

[24] Kerber, Adalbert Representations of permutation groups. I 1971

[25] Knuth, Donald E. The art of computer programming 1975

[26] Knuth, Donald E. The art of computer programming 1975

[27] Logan, B. F., Shepp, L. A. A variational problem for random Young tableaux Advances in Math. 1977 206 222

[28] Rockmore, Daniel Fast Fourier analysis for abelian group extensions Adv. in Appl. Math. 1990 164 204

[29] Probability, statistical mechanics, and number theory 1986

[30] Regev, Amitai Asymptotic values for degrees associated with strips of Young diagrams Adv. in Math. 1981 115 136

[31] Rockmore, Daniel Computation of Fourier transforms on the symmetric group 1989 156 165

[32] Rothaus, Oscar, Thompson, John G. A combinatorial problem in the symmetric group Pacific J. Math. 1966 175 178

[33] Serre, Jean-Pierre Linear representations of finite groups 1977

[34] Stanton, Dennis Orthogonal polynomials and Chevalley groups 1984 87 128

[35] Vershik, A. M., Kerov, S. V. Asymptotic theory of the characters of a symmetric group Funktsional. Anal. i Prilozhen. 1981

[36] Winograd, S. On computing the discrete Fourier transform Math. Comp. 1978 175 199

Cité par Sources :