Improved upper complexity bounds for the discrete Fourier transform
type: Item
instance of: scholarly article
title: Improved upper complexity bounds for the discrete Fourier transform
zbMATH Open document ID: 0734.65103
DOI: 10.1007/BF01810853
author: Ulrich Baum
author: Michael Clausen
author: Benno Tietz
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 1991-01-01T00:00:00Z
review text: By investigating several classical fast Fourier transform algorithms, this paper evaluates the upper bounds \(L_ 2(G)|_{\max}\), such that \(L_ 2(G)|_{\max}\leq 8| G| \log_ 2| G|\) in the discrete Fourier transform on any finite metabelian group G.
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 4215337
zbMATH Keywords: group algebra
zbMATH Keywords: linear complexity
zbMATH Keywords: fast Fourier transform
zbMATH Keywords: discrete Fourier transform
MaRDI profile type: Publication
cites work: The complexity of group algebra computations
cites work: Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
cites work: Q3321411
cites work: On the computational complexity of the general discrete Fourier transform
cites work: Fast Fourier Transforms for Metabelian Groups
cites work: Fast generalized Fourier transforms
cites work: An Algorithm for the Machine Calculation of Complex Fourier Series
cites work: A generalization of spectral analysis with application to ranked data
cites work: Efficient Computation of the Fourier Transform on Finite Groups
cites work: Q3675490
cites work: Endliche Gruppen I
cites work: Q3765707
cites work: Fast Fourier Transforms on Finite Non-Abelian Groups
cites work: Q3026944
cites work: Fast Fourier transform and convolution algorithms
cites work: Fast Fourier analysis for abelian group extensions
cites work: Q4728532
cites work: On computing the Discrete Fourier Transform
cites work: Q3883493
full work available at URL: https://doi.org/10.1007/bf01810853
OpenAlex ID: W2019435258
description: scientific article; zbMATH DE number 4215337