Separation of variables and the computation
of Fourier transforms on finite groups, I
Authors: David K. Maslen and Daniel N. Rockmore
Journal: J. Amer. Math. Soc. 10 (1997), 169-214
MSC (1991): Primary 20C15; Secondary 65T10
MathSciNet review: 1396896
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.
David K. Maslen
Affiliation: Max-Planck-Institut für Mathematik, 53225 Bonn, Germany
Address at time of publication: Department of Mathematics, Universiteit Utrecht, 3584 CD, Utrecht Netherlands
Daniel N. Rockmore
Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755
Received by editor(s): March 8, 1996
Received by editor(s) in revised form: May 23, 1996
Additional Notes: A preliminary version of some of this work appears as an extended abstract in the Proceedings of the 1995 ACM-SIAM Symposium on Discrete Algorithms, pp. 253–262
Maslen was partially supported as a Shapiro Visitor while at Dartmouth. Rockmore was partially supported by ARPA as administered by the AFOSR under contract DOD F4960-93-1-0567 as well as NSF DMS Award 9404275 and an NSF Presidential Faculty Fellowship.
Article copyright: © Copyright 1997 American Mathematical Society