Computation of Fourier Transforms on the Symmetric Group

Let G be a finite group and f any complex-valued function defined on G. If p is a matrix representation of G then the Fourier transform of f at p is defined as the matrix ∑s∊Gf(s)p(s)-Various applications demand the computation of the Fourier transforms of f at all irreducible representations of G. Direct computation of all such Fourier transforms requires on the order of |G|2 arithmetic operations.In earlier work with Diaconis ([DR]) ideas have been presented for more efficient methods of computing Fourier transforms. In particular, for S_n several algorithms were sketched. This paper describes in detail a running implementation of one of these algorithms which has been used effectively on a VAX11/750 and a SUN4.