Fast Fourier transforms for wreath products
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.
scientific article; zbMATH DE number 850660