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 then$M\_\{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