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

Maslen, David; Rockmore, Daniel

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

Separation of variables and the computation of Fourier transforms on finite groups, I
HTML articles powered by AMS MathViewer

by David K. Maslen and Daniel N. Rockmore

J. Amer. Math. Soc. 10 (1997), 169-214

DOI: https://doi.org/10.1090/S0894-0347-97-00219-1

PDF | Request permission

Abstract:

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.

References

E. F. Assmus Jr. and J. D. Key, Designs and their codes, Cambridge Tracts in Mathematics, vol. 103, Cambridge University Press, Cambridge, 1992. MR 1192126, DOI 10.1017/CBO9781316529836
M. D. Atkinson, The complexity of group algebra computations, Theoret. Comput. Sci. 5 (1977/78), no. 2, 205–209. MR 483650, DOI 10.1016/0304-3975(77)90007-X
L. Auslander and R. Tolimieri, Is computing with the finite Fourier transform pure or applied mathematics?, Bull. Amer. Math. Soc. (N.S.) 1 (1979), no. 6, 847–897. MR 546312, DOI 10.1090/S0273-0979-1979-14686-X
L. Babai, K. Freidl and M. Stricker, Decomposition of *-closed algebras in polynomial time, Proc. $18^{\text {th}}$ ACM ISSAC (1993), 86–94.
L. Babai, E. Luks, and A. Seress, Fast management of permutation groups, Proc. $28^{\text {th}}$ IEEE FOCS (1988), 272–282.
László Babai and Lajos Rónyai, Computing irreducible representations of finite groups, Math. Comp. 55 (1990), no. 192, 705–722. MR 1035925, DOI 10.1090/S0025-5718-1990-1035925-1
Ulrich Baum, Existence and efficient construction of fast Fourier transforms on supersolvable groups, Comput. Complexity 1 (1991), no. 3, 235–256. MR 1165193, DOI 10.1007/BF01200062
Ulrich Baum and Michael Clausen, Some lower and upper complexity bounds for generalized Fourier transforms and their inverses, SIAM J. Comput. 20 (1991), no. 3, 451–459. MR 1094524, DOI 10.1137/0220028
Ulrich Baum, Michael Clausen, and Benno Tietz, Improved upper complexity bounds for the discrete Fourier transform, Appl. Algebra Engrg. Comm. Comput. 2 (1991), no. 1, 35–43. MR 1209242, DOI 10.1007/BF01810853
R. Beals and L. Babai, Las Vegas algorithms for matrix groups, Proc. $34^{\text {th}}$ IEEE FOCS (1993), 427–436.
Laurel Beckett and Persi Diaconis, Spectral analysis for discrete longitudinal data, Adv. Math. 103 (1994), no. 1, 107–128. MR 1257214, DOI 10.1006/aima.1994.1002
Thomas Beth, On the computational complexity of the general discrete Fourier transform, Theoret. Comput. Sci. 51 (1987), no. 3, 331–339. MR 909461, DOI 10.1016/0304-3975(87)90041-7
Thomas Beth, Verfahren der schnellen Fourier-Transformation, Leitfäden der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics], vol. 61, B. G. Teubner, Stuttgart, 1984 (German). Die allgemeine diskrete Fourier-Transformation—ihre algebraische Beschreibung, Komplexität und Implementierung [The general discrete Fourier transform—its algebraic description, complexity and implementation]; Teubner Studienbücher Informatik. [Teubner Textbooks in Computer Science]. MR 753642
Seminar on Algebraic Groups and Related Finite Groups. (Held at The Institute for Advanced Study, Princeton, N. J., 1968/69), Lecture Notes in Mathematics, Vol. 131, Springer-Verlag, Berlin-New York, 1970. MR 0258840
Roger W. Carter, Simple groups of Lie type, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1989. Reprint of the 1972 original; A Wiley-Interscience Publication. MR 1013112
Roger W. Carter, Finite groups of Lie type, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1985. Conjugacy classes and complex characters; A Wiley-Interscience Publication. MR 794307
Michael Clausen, Fast Fourier transforms for metabelian groups, SIAM J. Comput. 18 (1989), no. 3, 584–593. MR 996838, DOI 10.1137/0218040
Michael Clausen, Fast generalized Fourier transforms, Theoret. Comput. Sci. 67 (1989), no. 1, 55–63. MR 1015084, DOI 10.1016/0304-3975(89)90021-2
—, Beiträge zum Entwurf schneller Spektraltransformationen, Habilitationsschrift, Fakultät für Informatik der Universität Karlsruhe (TH), 1988.
Michael Clausen and Ulrich Baum, Fast Fourier transforms, Bibliographisches Institut, Mannheim, 1993. MR 1270670
Michael Clausen and Ulrich Baum, Fast Fourier transforms for symmetric groups: theory and implementation, Math. Comp. 61 (1993), no. 204, 833–847. MR 1192969, DOI 10.1090/S0025-5718-1993-1192969-X
J. Cooley, The re-discovery of the fast Fourier transform algorithm, Mikrochimica Acta III (1987), 33–45.
—, How the FFT gained acceptance, Proceedings of the ACM Conference on the History of Scientific and Numeric Computation, Princeton, NJ May 13–15, 1987, 133–140.
James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 178586, DOI 10.1090/S0025-5718-1965-0178586-1
P. Deligne and G. Lusztig, Representations of reductive groups over finite fields, Ann. of Math. (2) 103 (1976), no. 1, 103–161. MR 393266, DOI 10.2307/1971021
Persi Diaconis, A generalization of spectral analysis with application to ranked data, Ann. Statist. 17 (1989), no. 3, 949–979. MR 1015133, DOI 10.1214/aos/1176347251
Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069, DOI 10.1007/BFb0086177
Persi Diaconis and Daniel Rockmore, Efficient computation of isotypic projections for the symmetric group, Groups and computation (New Brunswick, NJ, 1991) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, RI, 1993, pp. 87–104. MR 1235796, DOI 10.1090/dimacs/011/06
Persi Diaconis and Daniel Rockmore, Efficient computation of the Fourier transform on finite groups, J. Amer. Math. Soc. 3 (1990), no. 2, 297–332. MR 1030655, DOI 10.1090/S0894-0347-1990-1030655-4
James R. Driscoll and Dennis M. Healy Jr., Computing Fourier transforms and convolutions on the $2$-sphere, Adv. in Appl. Math. 15 (1994), no. 2, 202–250. MR 1277214, DOI 10.1006/aama.1994.1008
Douglas F. Elliott and K. Ramamohan Rao, Fast transforms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1982. Algorithms, analyses, applications. MR 696936
A. Fässler and E. Stiefel, Group theoretical methods and their applications, Birkhäuser Boston, Inc., Boston, MA, 1992. Translated from the German by Baoswan Dzung Wong. MR 1158662, DOI 10.1007/978-1-4612-0395-7
I. M. Gel’fand and M. Tsetlin, Finite dimensional representations of the group of unimodular matrices, Dokl. Akad. Nauk SSSR 71 (1950), 825–828 (Russian).
Frederick M. Goodman, Pierre de la Harpe, and Vaughan F. R. Jones, Coxeter graphs and towers of algebras, Mathematical Sciences Research Institute Publications, vol. 14, Springer-Verlag, New York, 1989. MR 999799, DOI 10.1007/978-1-4613-9641-3
T. Hagedorn, Multiplicities in restricted representations, Ph.D. Thesis, Department of Mathematics, Harvard University, 1994.
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911, DOI 10.21236/AD0705364
D. Healy, D. Maslen, S. Moore, D. Rockmore and M. Taylor, Applications of a fast convolution algorithm on the 2-sphere, Technical Report, Department of Mathematics and Computer Science, Dartmouth College, 1994.
Michael T. Heideman, Don H. Johnson, and C. Sidney Burrus, Gauss and the history of the fast Fourier transform, Arch. Hist. Exact Sci. 34 (1985), no. 3, 265–277. MR 815154, DOI 10.1007/BF00348431
Howard Hiller, Geometry of Coxeter groups, Research Notes in Mathematics, vol. 54, Pitman (Advanced Publishing Program), Boston, Mass.-London, 1982. MR 649068
G. D. James, The representation theory of the symmetric groups, Lecture Notes in Mathematics, vol. 682, Springer, Berlin, 1978. MR 513828, DOI 10.1007/BFb0067708
G. D. James, Representations of general linear groups, London Mathematical Society Lecture Note Series, vol. 94, Cambridge University Press, Cambridge, 1984. MR 776229, DOI 10.1017/CBO9780511661921
M. G. Karpovsky, Fast Fourier transforms on finite non-abelian groups, IEEE Trans. Comput. C-26 (1977), no. 10, 1028–1030. MR 497262, DOI 10.1109/tc.1977.1674739
Mark G. Karpovsky (ed.), Spectral techniques and fault detection, Notes and Reports in Computer Science and Applied Mathematics, vol. 11, Academic Press, Inc., Orlando, FL, 1985. MR 818746
Adalbert Kerber, Representations of permutation groups. I, Lecture Notes in Mathematics, Vol. 240, Springer-Verlag, Berlin-New York, 1971. MR 0325752, DOI 10.1007/BFb0067943
N. Ja. Vilenkin and A. U. Klimyk, Representation of Lie groups and special functions. Vol. 1, Mathematics and its Applications (Soviet Series), vol. 72, Kluwer Academic Publishers Group, Dordrecht, 1991. Simplest Lie groups, special functions and integral transforms; Translated from the Russian by V. A. Groza and A. A. Groza. MR 1143783, DOI 10.1007/978-94-011-3538-2
John D. Lafferty and Daniel Rockmore, Fast Fourier analysis for $\textrm {SL}_2$ over a finite field and related numerical experiments, Experiment. Math. 1 (1992), no. 2, 115–139. MR 1203870, DOI 10.1080/10586458.1992.10504252
Stephen A. Linton, Gerhard O. Michler, and Jørn B. Olsson, Fourier transforms with respect to monomial representations, Math. Ann. 297 (1993), no. 2, 253–268. MR 1241805, DOI 10.1007/BF01459500
D. Maslen, Efficient computation of Fourier transforms on compact groups, Max-Planck preprint MPI/95-8 (1995).
D. Maslen and D. Rockmore Generalized FFTs - a survey of some recent results, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Groups and Computation, II, L. Finkelstein and W. Kantor (eds.), (to appear).
—, Separation of variables and the efficient computation of Fourier transforms on finite groups, II, (in preparation).
David K. Maslen and Daniel N. Rockmore, Adapted diameters and the efficient computation of Fourier transforms on finite groups, Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1995) ACM, New York, 1995, pp. 253–262. MR 1321855
J. A. Nelder, The analysis of randomized experiments with orthogonal block structure. I. Block structure and the null analysis of variance, Proc. Roy. Soc. London Ser. A 283 (1965), 147–162. MR 176576, DOI 10.1098/rspa.1965.0012
A. Oppenheim and R. Schafer, Discrete-time signal processing. Prentice Hall, NJ, 1989.
D. Rockmore Some applications of generalized FFTs, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Groups and Computation, II, L. Finkelstein and W. Kantor (eds.), (to appear).
—, Fast Fourier transforms for wreath products, Appl. Comput. Harmon. Anal. 4 (1995), 34–55.
Daniel N. Rockmore, Efficient computation of Fourier inversion for finite groups, J. Assoc. Comput. Mach. 41 (1994), no. 1, 31–66. MR 1369193, DOI 10.1145/174644.174646
Daniel Rockmore, Fast Fourier analysis for abelian group extensions, Adv. in Appl. Math. 11 (1990), no. 2, 164–204. MR 1053228, DOI 10.1016/0196-8858(90)90008-M
Jean-Pierre Serre, Linear representations of finite groups, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott. MR 0450380, DOI 10.1007/978-1-4684-9458-7
Charles C. Sims, Computational methods in the study of permutation groups, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 169–183. MR 0257203
Richard Stong, Some asymptotic results on finite vector spaces, Adv. in Appl. Math. 9 (1988), no. 2, 167–199. MR 937520, DOI 10.1016/0196-8858(88)90012-7
Elmar Thoma, Die Einschränkung der Charaktere von $\textrm {GL}(n,\,q)$ auf $\textrm {GL}(n-1,\,q)$, Math. Z. 119 (1971), 321–338 (German). MR 288190, DOI 10.1007/BF01109884
Richard Tolimieri, Myoung An, and Chao Lu, Algorithms for discrete Fourier transform and convolution, Springer-Verlag, New York, 1989. MR 1201161, DOI 10.1007/978-1-4757-3854-4
Charles Van Loan, Computational frameworks for the fast Fourier transform, Frontiers in Applied Mathematics, vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1153025, DOI 10.1137/1.9781611970999
G. E. Wall, On the conjugacy classes in the unitary, symplectic and orthogonal groups, J. Austral. Math. Soc. 3 (1963), 1–62. MR 0150210, DOI 10.1017/S1446788700027622
A. Willsky, On the algebraic structure of certain partially observable finite-state Markov processes, Inform. Contr. 38 (1978), 179–212.
Shmuel Winograd, Arithmetic complexity of computations, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 33, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1980. MR 565260, DOI 10.1137/1.9781611970364
C. M. Woodman. The symmetry groups of non-rigid molecules as semi-direct products, Mol. Phys. (6)19 (1970), 753–780.
Andrey V. Zelevinsky, Representations of finite classical groups, Lecture Notes in Mathematics, vol. 869, Springer-Verlag, Berlin-New York, 1981. A Hopf algebra approach. MR 643482, DOI 10.1007/BFb0090287