Fast Fourier transforms for wreath products
type: Item
instance of: scholarly article
title: Fast Fourier transforms for wreath products
zbMATH Open document ID: 0841.65141
author: Daniel N. Rockmore
published in: Applied and Computational Harmonic Analysis
publication date: 1996-07-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 20E22
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 850660
zbMATH Keywords: (subgroup)-adapted bases
zbMATH Keywords: linear complexity
zbMATH Keywords: fast Fourier transform algorithms
zbMATH Keywords: wreath products
zbMATH Keywords: data analysis
reviewed by: Yasuhiro Kobayashi
MaRDI profile type: Publication
OpenAlex ID: W2078992516
DOI: 10.1006/ACHA.1995.1020
description: scientific article; zbMATH DE number 850660