Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform

ABSTRACT

A lower bound for the number of additions necessary to compute a family of linear functions by a linear algorithm is given when an upper bound c can be assigned to the modulus of the complex numbers involved in the computation. In the case of the fast Fourier transform, the lower bound is (n/2) log2n when c = 1.

REFERENCES

• 1: MORGENSTERN, J. Algorithmes lindaires. Compt. Rend. Acad. Sci. 272, 1059-1060.
• 2: MORGE~S~ERN, J. On linear algorithms. In Theory of Machines and Computations, Academic Press, New York and London, 1971, pp. 59-66.
• 3: QVEYSANNE, M. Ag~bre M.G.P. Collection U. Armand Colin, Paris, 1966, Exercice No. 258, p. 363.
• 4: COOLEY, J. W, AND TUKEY, J.W. An algorithm for the machine computation of complex Fourier series. Math. Comp. 19 (1964), 297-301.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Performance, Theory, Verification