Efficient Computation of the Fourier Transform on Finite Groups

Abstract

Let G be a finite group.Let f: G -> C be a function.To each irreducible representation p of G there is associated a Fourier transforminvolves order IGld~ operations (multiplications and additions).Direct computation of the Feurier transform for all irreducible representations involves order IGI Lp d~ = IGI2 operations.For Abelian groups, such as the integers mod n or the group of binary ntuples, substantial speedups have been achieved.Fast Fourier transforms allow computation in order IGIIog IGI operations.These ideas have been important in theoretical computer science where they have been applied to give fast algorithms for a variety of tasks ranging from multiplication of numbers to evaluation of polynomials.The algorithms offer substantial practical savings, and have revolutionized spectral analysis throughout engineering and the sciences.Aho, Hopcroft, andUllman (1976), andElliott andRao (1982) contain reviews with extensive pointers to the literature.This paper presents several algorithms that allow impressive speedups in theory and practice.The basic ideas are outlined in 2 which also shows how they reduce to the Cooley-Tukey algorithm for the integers mod n .In brief, if a representation p is restricted to a subgroup, it splits up into irreducible representations.With an appropriate basis, p can be written in block diagonal form and the transform at p can be built up as a direct sum of transforms over the subgroup.This can be iterated.It yields a family of algorithms that all take fewer operations than direct computation.