Improved upper complexity bounds for the discrete Fourier transform (Q811112): Difference between revisions

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.

0 references

zbMATH Keywords

group algebra

0 references

linear complexity

0 references

fast Fourier transform

0 references

discrete Fourier transform

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

The complexity of group algebra computations

0 references

Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses

0 references

Q3321411

0 references

On the computational complexity of the general discrete Fourier transform

0 references

Fast Fourier Transforms for Metabelian Groups

0 references

Fast generalized Fourier transforms

0 references

An Algorithm for the Machine Calculation of Complex Fourier Series

0 references

A generalization of spectral analysis with application to ranked data

0 references

Efficient Computation of the Fourier Transform on Finite Groups

0 references

Q3675490

0 references

Endliche Gruppen I

0 references

Q3765707

0 references

Fast Fourier Transforms on Finite Non-Abelian Groups

0 references

Q3026944

0 references

Fast Fourier transform and convolution algorithms

0 references

Fast Fourier analysis for abelian group extensions

0 references

Q4728532

0 references

On computing the Discrete Fourier Transform

0 references

Q3883493

0 references

Identifiers

zbMATH Open document ID

0734.65103

0 references

DOI

10.1007/BF01810853

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:811112

@@ Property / cites work @@
+The complexity of group algebra computations
@@ Property / cites work: The complexity of group algebra computations / rank @@
+Normal rank
@@ Property / cites work @@
+Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
+Normal rank
@@ Property / cites work @@
+Q3321411
@@ Property / cites work: Q3321411 / rank @@
+Normal rank
@@ Property / cites work @@
+On the computational complexity of the general discrete Fourier transform
+Normal rank
@@ Property / cites work @@
+Fast Fourier Transforms for Metabelian Groups
@@ Property / cites work: Fast Fourier Transforms for Metabelian Groups / rank @@
+Normal rank
@@ Property / cites work @@
+Fast generalized Fourier transforms
@@ Property / cites work: Fast generalized Fourier transforms / rank @@
+Normal rank
@@ Property / cites work @@
+An Algorithm for the Machine Calculation of Complex Fourier Series
+Normal rank
@@ Property / cites work @@
+A generalization of spectral analysis with application to ranked data
+Normal rank
@@ Property / cites work @@
+Efficient Computation of the Fourier Transform on Finite Groups
+Normal rank
@@ Property / cites work @@
+Q3675490
@@ Property / cites work: Q3675490 / rank @@
+Normal rank
@@ Property / cites work @@
+Endliche Gruppen I
@@ Property / cites work: Endliche Gruppen I / rank @@
+Normal rank
@@ Property / cites work @@
+Q3765707
@@ Property / cites work: Q3765707 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Fourier Transforms on Finite Non-Abelian Groups
+Normal rank
@@ Property / cites work @@
+Q3026944
@@ Property / cites work: Q3026944 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Fourier transform and convolution algorithms
@@ Property / cites work: Fast Fourier transform and convolution algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Fourier analysis for abelian group extensions
+Normal rank
@@ Property / cites work @@
+Q4728532
@@ Property / cites work: Q4728532 / rank @@
+Normal rank
@@ Property / cites work @@
+On computing the Discrete Fourier Transform
@@ Property / cites work: On computing the Discrete Fourier Transform / rank @@
+Normal rank
@@ Property / cites work @@
+Q3883493
@@ Property / cites work: Q3883493 / rank @@
+Normal rank