Abstract
The linear complexityL 2 (G) of a finite groupG is the minimal number of additions, subtractions and multiplications by complex constants of absolute value ≦2 sufficient to evaluate a suitable Fourier transform of ℂG. Combining and modifying several classical FFT-algorithms, we show thatL 2(G)≦8|G|log2|G| for any finite metabelian groupG.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Atkinson, M. D.: The complexity of group algebra computations. Theor. Comp. Sci.5, 205–209 (1977)
Baum, U., Clausen, M.: Some lower and upper complexity bounds for generalized Fourier transforms and their inverses. SIAM J. Comput. (to appear)
Beth, T.: Verfahren der schnellen Fourier-Transformation. Stuffgart: Teubner 1984
Beth, T.: On the computational complexity of the general discrete Fourier transform. Theor. Comp. Sci.51, 331–339 (1987)
Bluestein, L. I.: A linear filtering approach to the computation of the discrete Fourier transform. IEEE Trans.AU-18, 451–455 (1970)
Büchi, W.: Die diskrete Fourier transformation. Diplomarbeit, Universität Zürich, 1979
Clausen, M.: Fast Fourier Transforms for Metabelian Groups. SIAM J. Comput.18, 584–593 (1989)
Clausen, M.: Fast generalized Fourier transforms. Theor. Comp. Sci.67, 55–63 (1989)
Cooley, J. W., Tukey, J. W.: An algorithm for the machine calculation of complex Fourier series. Math. Comp.19, 297–301 (1965)
Diaconis, P.: Spectral analysis for ranked data. Ann. Statistics (to appear)
Diaconis, P., Rockmore, D.: Efficient computation of the Fourier transform on finite groups. Technical Report, Stanford University, April 1988
Elliott, D. F., Rao, K. R.: Fast transforms. New York: Academic Press 1982
Huppert, B.: Endliche Gruppen I. Berlin, Heidelberg, New York: Springer 1967
Hurst, S. L., Miller, D. M., Muzio, J. C.: Spectral techniques in digital logic. New York: Academic Press 1985
Karpovsky, M. G.: Fast Fourier transforms on finite non-abelian groups. IEEE Trans. Comput.26/10, 1028–1030 (1977)
Karpovsky, M. G. (ed.): Spectral techniques and fault detection. New York: Academic Press 1985
Nussbaumer, H. J.: Fast Fourier transform and convolution algorithms. Berlin, Heidelberg, New York: Springer 1981
Rader, C. M.: Discrete Fourier transform when the number of data points is prime. Proc. IEEE56, 1107–1108 (1968)
Rockmore, D.: Fast Fourier analysis for abelian group extensions. Adv. Appl. Math.11, 164–204 (1990)
Rockmore, D.: Computation of Fourier transforms on the symmetric group. In: Kaltofen, E., Watt, S. M. (eds.) Computers in Mathematics. Berlin, Heidelberg, New York: Springer 1989
Winograd, S.: On computing the discrete Fourier transform. Proc. Nat. Acad. Sci. USA73, 1005–1006 (1976)
Winograd, S.: Arithmetic complexity of computations. SIAM, 1980
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Baum, U., Clausen, M. & Tietz, B. Improved upper complexity bounds for the discrete fourier transform. AAECC 2, 35–43 (1991). https://doi.org/10.1007/BF01810853
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01810853