Fast Fourier transforms for wreath products (Q1908143)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fast Fourier transforms for wreath products |
scientific article |
Statements
Fast Fourier transforms for wreath products (English)
0 references
1 July 1996
0 references
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.
0 references
(subgroup)-adapted bases
0 references
linear complexity
0 references
fast Fourier transform algorithms
0 references
wreath products
0 references
data analysis
0 references