Arithmetic complexity of the discrete Fourier transform

From Wikipedia, the free encyclopedia

You have new messages (last change).
This article may require cleanup to meet Wikipedia's quality standards.
Please discuss this issue on the talk page or replace this tag with a more specific message.
This article has been tagged since December 2006.

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

[edit] 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 MDFT(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} piei where pi, i=1,...,m are distinct primes and ei, i=1,...,m are positive integers, it follows then M_{DFT}(N)=2N-\sum_{i_1=0}^{e_1}\sum_{i_2=0}^{e_2}\ldots\sum_{i_m=0}^{e_m}\phi(gcd(\prod_{i=1}^{m}p_j^{i_j},4)).

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

where φ(.) 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.
N 2 3 4 5 6 8 12 16 24 32 48 64 128 256
definition 4 9 16 25 36 64 144 256 576 1024 2304 4096 16384 65536
FFT 2 * 8 * * 24 * 64 * 160 * 384 896 2048
MDFT(N) 0 1 0 4 2 2 4 10 12 32 38 84 198 438

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.

[edit] 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
Retrieved from "http://en.wikipedia.org../../../a/r/i/Arithmetic_complexity_of_the_discrete_Fourier_transform_b0be.html"