Arithmetic complexity of the discrete Fourier transform


Arithmetic complexity of the discrete Fourier transform

See Fast Fourier transform#Bounds on complexity and operation counts for a general summary of this issue.

Bounds on the multiplicative complexity of FFT

In his PhD thesis in 1987 [1] , 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" [2] .

Theorem (Heidman). For a given N=prod_{i=1}^{m} "p"i"e""i" where "p"i, i=1,...,"m" are distinct primes and "e""i", "i" = 1, ..., "m" are positive integers, it follows thenM_{DFT}(N)=2N-sum_{i_1=0}^{e_1}sum_{i_2=0}^{e_2}ldotssum_{i_m=0}^{e_m}phi(operatorname{gcd}(prod_{i=1}^{m}p_j^{i_j},4)).

(1+sum_{d_1|frac{phi(p_1^{i_1})}{phi(operatorname{gcd}(p_1^{i_1},4)sum_{d_2|frac{phi(p_2^{i_2})}{phi(operatorname{gcd}(p_2^{i_2},4)ldots sum_{d_m|frac{phi(p_m^{i_m})}{phi(operatorname{gcd}(p_m^{i_m},4)frac{prod_{k=1}^{m}phi(d_k)}{phi (lcm(d_1,d_2,ldots,d_m)})

where phi(.) is the Euler's totient function function, gcd(.,.) denotes the greatest common divisor and 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-point multiplications) required for computing a DFT for a few selected blocklengths."

Recently, a new fast Fourier transform algorithm was introduced [3,4] , which is based on a multilayer Hadamard decomposition so as to evaluate a DFT via a discrete Hartley transform (DHT), which achieve the minimal floating-point multiplicative complexity for blocklengths until "N" = 24.

References

* [1] M.T. Heidman, "Multiplicative Complexity, Convolution and the DFT", Springer-Verlag, 1988.

* [2] 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.

* [3] 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.

* [4] 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


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.