- Arithmetic complexity of the discrete Fourier transform
Fast Fourier transform#Bounds on complexity and operation countsfor a general summary of this issue.
Bounds on the multiplicative complexity of FFT
In his PhD thesis in 1987  , Michael Heidman focus on the arithmetic theory of complexity for a
Discrete Fourier transform(DFT) and hit upon remarkable results. Among them, a lower bound for the multiplicative (floating-point) complexity required to compute discrete transforms, which is presented below. Let us denote by "M"DFT("N") the minimal multiplicative complexity for the exact computing a DFT of blocklength "N"  .
Theorem (Heidman). For a given "p"i"e""i" where "p"i, i=1,...,"m" are distinct primes and "e""i", "i" = 1, ..., "m" are positive integers, it follows then
where (.) is the
Euler's totient functionfunction, gcd(.,.) denotes the greatest common divisorand lcm(.,.) is the least common multiple. Proof. See [1, page 98] .
The application of this theorem for several values of "N" yields the complexities shown on the table. The difference between pointed complexities is striking. A further point to be observed is the fact that some people believe that
Fast Fourier transform(FFT, Cooley-Tukey) is a close-to-optimum algorithm for computing a DFT. This minimal complexity is the same as that one required for the Discrete Hartley transform(DHT) of the same blocklength.
:: "Table I - Minimal multiplicative complexity (expressed as the number of
floating-pointmultiplications) required for computing a DFT for a few selected blocklengths."
Recently, a new
fast Fourier transformalgorithm was introduced [3,4] , which is based on a multilayer Hadamard decomposition so as to evaluate a DFTvia a discrete Hartley transform(DHT), which achieve the minimal floating-point multiplicative complexity for blocklengths until "N" = 24.
*  M.T. Heidman, "Multiplicative Complexity, Convolution and the DFT", Springer-Verlag, 1988.
*  M.T. Heideman and C. Sidney Burrus, 1986, On the number of multiplications necessary to compute a length-2n DFT, "IEEE Trans. Acoust. Speech. Sig. Proc.", vol.34: pp.91-95.
*  H.M. de Oliveira, R.J.S. Cintra, R.M.C. Souza, Multilevel Hadamard Decomposition of Discrete Hartley Transforms, In: "Annals of the Brazilian Symposium on Telecommunications", XVIII Simpósio Brasileiro de Telecomunicações, Gramado, RS. Brazil, 2000.
*  Ibdem, A Factorization Scheme for Discrete Hartley Transform Matrices, In: International Conference on System Engineering, Comm. and Inform. Technologies, "Proc. of the ICSECIT (Int. Conf. on System Engineering, Comm. and Info. Technol.). "Punta Arenas, 2001. http://www2.ee.ufpe.br/codec/1_01.pdf
Wikimedia Foundation. 2010.
Look at other dictionaries:
Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… … Wikipedia
Discrete cosine transform — A discrete cosine transform (DCT) expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy… … Wikipedia
Discrete sine transform — In mathematics, the discrete sine transform (DST) is a Fourier related transform similar to the discrete Fourier transform (DFT), but using a purely real matrix. It is equivalent to the imaginary parts of a DFT of roughly twice the length,… … Wikipedia
Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group … Wikipedia
Modified discrete cosine transform — The modified discrete cosine transform (MDCT) is a Fourier related transform based on the type IV discrete cosine transform (DCT IV), with the additional property of being lapped: it is designed to be performed on consecutive blocks of a larger… … Wikipedia
List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A … Wikipedia
Schönhage-Strassen algorithm — The Schönhage Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. [A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen ,… … Wikipedia
Cooley–Tukey FFT algorithm — The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 in terms of smaller DFTs… … Wikipedia
Cooley-Tukey FFT algorithm — The Cooley Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N 1 N 2 in terms of smaller… … Wikipedia
List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra … Wikipedia