Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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 PDF
J. Amer. Math. Soc. 10 (1997), 169-214 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
Similar Articles
  • Retrieve articles in Journal of the American Mathematical Society with MSC (1991): 20C15, 65T10
  • Retrieve articles in all journals with MSC (1991): 20C15, 65T10
Additional Information
  • 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
  • Email: maslen@math.ruu.nl
  • Daniel N. Rockmore
  • Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755
  • Email: rockmore@cs.dartmouth.edu
  • 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.
  • © Copyright 1997 American Mathematical Society
  • Journal: J. Amer. Math. Soc. 10 (1997), 169-214
  • MSC (1991): Primary 20C15; Secondary 65T10
  • DOI: https://doi.org/10.1090/S0894-0347-97-00219-1
  • MathSciNet review: 1396896