Separation of variables and the computation of Fourier transforms on finite groups, I

Maslen, David^1, 2 ; Rockmore, Daniel³

¹ Max-Planck-Institut für Mathematik, 53225 Bonn, Germany
² Department of Mathematics, Universiteit Utrecht, 3584 CD, Utrecht Netherlands
³ Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755

Journal of the American Mathematical Society, Tome 10 (1997) no. 1, pp. 169-214

Résumé

This paper introduces new techniques for the efficient computation of a Fourier transform on a finite group. We present a divide and conquer approach to the computation. The divide aspect uses factorizations of group elements to reduce the matrix sum of products for the Fourier transform to simpler sums of products. This is the separation of variables algorithm. The conquer aspect is the final computation of matrix products which we perform efficiently using a special form of the matrices. This form arises from the use of subgroup-adapted representations and their structure when evaluated at elements which lie in the centralizers of subgroups in a subgroup chain. We present a detailed analysis of the matrix multiplications arising in the calculation and obtain easy-to-use upper bounds for the complexity of our algorithm in terms of representation theoretic data for the group of interest. Our algorithm encompasses many of the known examples of fast Fourier transforms. We recover the best known fast transforms for some abelian groups, the symmetric groups and their wreath products, and the classical Weyl groups. Beyond this, we obtain greatly improved upper bounds for the general linear and unitary groups over a finite field, and for the classical Chevalley groups over a finite field. We also apply these techniques to obtain analogous results for homogeneous spaces. This is part I of a two part paper. Part II will present a refinement of these techniques which yields further savings.

Détail

DOI : 10.1090/S0894-0347-97-00219-1

Bibliographie

[1] Assmus, E. F., Jr., Key, J. D. Designs and their codes 1992

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

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

[4] Babai, Lã¡Szlã³, Rã³Nyai, Lajos Computing irreducible representations of finite groups Math. Comp. 1990 705 722

[5] Baum, Ulrich Existence and efficient construction of fast Fourier transforms on supersolvable groups Comput. Complexity 1991 235 256

[6] Baum, Ulrich, Clausen, Michael Some lower and upper complexity bounds for generalized Fourier transforms and their inverses SIAM J. Comput. 1991 451 459

[7] Baum, Ulrich, Clausen, Michael, Tietz, Benno Improved upper complexity bounds for the discrete Fourier transform Appl. Algebra Engrg. Comm. Comput. 1991 35 43

[8] Beckett, Laurel, Diaconis, Persi Spectral analysis for discrete longitudinal data Adv. Math. 1994 107 128

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

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

[11] Seminar on Algebraic Groups and Related Finite Groups. (Held at The Institute for Advanced Study, Princeton, N. J., 1968/69) 1970

[12] Carter, Roger W. Simple groups of Lie type 1989

[13] Carter, Roger W. Finite groups of Lie type 1985

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

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

[16] Clausen, Michael, Baum, Ulrich Fast Fourier transforms 1993

[17] Clausen, Michael, Baum, Ulrich Fast Fourier transforms for symmetric groups: theory and implementation Math. Comp. 1993 833 847

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

[19] Deligne, P., Lusztig, G. Representations of reductive groups over finite fields Ann. of Math. (2) 1976 103 161

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

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

[22] Diaconis, Persi, Rockmore, Daniel Efficient computation of isotypic projections for the symmetric group 1993 87 104

[23] Diaconis, Persi, Rockmore, Daniel Efficient computation of the Fourier transform on finite groups J. Amer. Math. Soc. 1990 297 332

[24] Driscoll, James R., Healy, Dennis M., Jr. Computing Fourier transforms and convolutions on the 2-sphere Adv. in Appl. Math. 1994 202 250

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

[26] Fã¤Ssler, A., Stiefel, E. Group theoretical methods and their applications 1992

[27] Goodman, Frederick M., De La Harpe, Pierre, Jones, Vaughan F. R. Coxeter graphs and towers of algebras 1989

[28] Harary, Frank Graph theory 1969

[29] Heideman, Michael T., Johnson, Don H., Burrus, C. Sidney Gauss and the history of the fast Fourier transform Arch. Hist. Exact Sci. 1985 265 277

[30] Hiller, Howard Geometry of Coxeter groups 1982

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

[32] James, G. D. Representations of general linear groups 1984

[33] Karpovsky, M. G. Fast Fourier transforms on finite non-abelian groups IEEE Trans. Comput. 1977 1028 1030

[34] Spectral techniques and fault detection 1985

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

[36] Vilenkin, N. Ja., Klimyk, A. U. Representation of Lie groups and special functions. Vol. 1 1991

[37] Lafferty, John D., Rockmore, Daniel Fast Fourier analysis for 𝑆𝐿₂ over a finite field and related numerical experiments Experiment. Math. 1992 115 139

[38] Linton, Stephen A., Michler, Gerhard O., Olsson, Jã¸Rn B. Fourier transforms with respect to monomial representations Math. Ann. 1993 253 268

[39] Maslen, David K., Rockmore, Daniel N. Adapted diameters and the efficient computation of Fourier transforms on finite groups 1995 253 262

[40] Nelder, J. A. The analysis of randomized experiments with orthogonal block structure. I. Block structure and the null analysis of variance Proc. Roy. Soc. London Ser. A 1965 147 162

[41] Rockmore, Daniel N. Efficient computation of Fourier inversion for finite groups J. Assoc. Comput. Mach. 1994 31 66

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

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

[44] Sims, Charles C. Computational methods in the study of permutation groups 1970 169 183

[45] Stong, Richard Some asymptotic results on finite vector spaces Adv. in Appl. Math. 1988 167 199

[46] Thoma, Elmar Die Einschränkung der Charaktere von 𝐺𝐿(𝑛,𝑞) auf 𝐺𝐿(𝑛-1,𝑞) Math. Z. 1971 321 338

[47] Tolimieri, Richard, An, Myoung, Lu, Chao Algorithms for discrete Fourier transform and convolution 1989

[48] Van Loan, Charles Computational frameworks for the fast Fourier transform 1992

[49] Wall, G. E. On the conjugacy classes in the unitary, symplectic and orthogonal groups J. Austral. Math. Soc. 1963 1 62

[50] Winograd, Shmuel Arithmetic complexity of computations 1980

[51] Zelevinsky, Andrey V. Representations of finite classical groups 1981