FAST FOURIER-TRANSFORMS FOR WREATH-PRODUCTS

In this paper fast Fourier transform algorithms (FFTs) are constructed for wreath products of the form G[S-n]. Examples of interest include the hyperoctahedral groups B-n (the symmetry groups of the n-cube) as well as more generally A[S-n] for any abelian groups A and also the fu ll wreath products S-m[S-n] and their iterates, often identified as au tomorphism groups of spherically homogeneous rooted trees. In general, direct computation of the discrete Fourier transform for any finite g roup H requires \H\2 operations. The algorithms presented in this pape r provide substantial speed-ups for general wreath products G[S-n], wh ich for the particular examples mentioned above reduce the \H\(2) boun d to O(\H\ log(4) \H\). Thus new classes of finite groups of close to minimal linear complexity are obtained. Applications to data analysis, signal processing and molecular spectroscopy are discussed. (C) 1995 Academic Press, Inc.