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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references