A Fast Program Generator of Fast Fourier Transforms

摘要

Let G be a finite group of order n. By Wedderburn's Theorem, the complex group algebra CG is isomorphic to an algebra of block diagonal matrices: CG approx= birect+(~h_(k_=1)) c=iC~((~d_k)x(~d_k)). Every such isomorphism D, a so-called discrete Fourier transform of CG, consists of a full set of pairwise inequivalent irreducible representations D_k of CG. A result of Morgenstern combined with the well-known Schur relations in representation theory show that (under mild conditions) any straight line program for evaluating a DFT needs at least Ω(n log n) operations. Thus in this model, every O(n log n) FFT of CG is optimal up to a constant factor. For the class of supersolvable groups we will discuss a program that from a pc-presentation of G constructs a DFT D =approx+(~D_k) of CG and generates an O(n log n) FFT of CG. The running time to construct D is essentially proportional to the time to write down all the monomial (!) twiddle factors D_k(gi) where the gi are the generators corresponding to the pc-presentation. Finally, we sketch some applications.