Fast Fourier transforms for wreath products (Q1908143)

Fast Fourier transform algorithms are constructed as wreath products by the symmetry groups of the \(n\)-cube. The wreath products are of interest in data analysis as the automorphism groups of spherically homogeneous rooted trees. The use of the wreath products can facilitate the computation. Thereby, the complexity of the transformation is improved upto \(O(|G|\log^4 |G|)\) operations for any abelian group \(G\). Note that in the direct transformation \(|G|^2\) operations are required.