On Computing the Discrete Fourier Transform

DOI10.2307/2006266zbMath0374.68034OpenAlexW4254389654MaRDI QIDQ4151723

Shmuel Winograd

Publication date: 1978

Full work available at URL: https://doi.org/10.2307/2006266

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Algorithms in computer science (68W99)

Related Items (42)

A COOLEY-TUKEY MODIFIED ALGORITHM IN FAST FOURIER TRANSFORM ⋮ Implementation of a self-sorting in-place prime factor FFT algorithm ⋮ A self-sorting in-place prime factor real/half-complex FFT algorithm ⋮ A new set of minimum-add small-n rotated DFT modules ⋮ Matrix decompositions using displacement rank and classes of commutative matrix algebras ⋮ Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. I: The algebra \(G[u/<Q(u)^{\ell}>\), \(\ell >1\)] ⋮ Efficient implementation of multidimensional fast Fourier transforms on a Cray X-MP ⋮ On algebras related to the discrete cosine transform ⋮ Index transforms for multidimensional DFT's and convolutions ⋮ Matrix displacement decompositions and applications to Toeplitz linear systems ⋮ Fast Fourier transformation based on number theoretic transforms ⋮ Hardness results and spectral techniques for combinatorial problems on circulant graphs ⋮ Fast norm computation in smooth-degree abelian number fields ⋮ A floating-point residue arithmetic unit ⋮ Matrix identities of the fast Fourier transform ⋮ On arithmetical algorithms over finite fields ⋮ Size bounds for superconcentrators ⋮ A simple derivation of Glassman's general N fast Fourier transform ⋮ Discrete convolution with modulo operations ⋮ Fast Fourier Transforms for Symmetric Groups: Theory and Implementation ⋮ Vector coding algorithms for multidimensional discrete Fourier transform ⋮ Generalization of the algebraic discrete Fourier transform with application to fast convolutions ⋮ Fast convolutions meet Montgomery ⋮ Lower triangular Toeplitz-Ramanujan systems whose solution yields the Bernoulli numbers ⋮ The multiplicative complexity of discrete cosine transforms ⋮ On the multiplicative complexity of the discrete Fourier transform ⋮ Efficient Computation of the Fourier Transform on Finite Groups ⋮ Multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields ⋮ Group Convolutions and Matrix Transforms ⋮ Discrete orthogonal function expansions for non-uniform grids using the fast Fourier transform ⋮ Modified Winograd FFT algorithm and its variants for transform size \(N=p^ k\) and their implementations ⋮ Nesting strategies for prime factor FFT algorithms ⋮ Self-sorting mixed-radix fast Fourier transforms ⋮ A note on prime factor FFT algorithms ⋮ In-place self-sorting fast Fourier transform algorithm with local memory references ⋮ Winograd's Fourier transform via circulants ⋮ Fast, prime factor, discrete Fourier transform algorithms over \(\text{GF}(2^m)\) for \(8 \leqslant m \leqslant 10\) ⋮ Ring structure and the Fourier transform ⋮ Abelian semi-simple algebras and algorithms for the discrete Fourier transform ⋮ Parallel multiplication and powering of polynomials ⋮ The differential Fourier transform method ⋮ Representation of real discrete Fourier transform in terms of a new set of functions based upon Möbius inversion

Cites Work

• Some bilinear forms whose multiplicative complexity depends on the field of constants
• Algebras Having Linear Multiplicative Complexities
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Unnamed Item
• Unnamed Item

This page was built for publication: On Computing the Discrete Fourier Transform