Fast Fourier Transforms for Wreath Products

AbstractIn this paper fast Fourier transform algorithms (FFTs) are constructed for wreath products of the form G[Sn]. Examples of interest include the hyperoctahedral groups Bn (the symmetry groups of the n-cube) as well as more generally A[Sn] for any abelian groups A and also the full wreath products Sm[Sn] and their iterates, often identified as automorphism groups of spherically homogeneous rooted trees. In general, direct computation of the discrete Fourier transform for any finite group H requires |H|2 operations. The algorithms presented in this paper provide substantial speed-ups for general wreath products G[Sn], which for the particular examples mentioned above reduce the |H|2 bound to O(|H| log4 |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