abstract
It is well-known that the product of two complex numbersX+iY andU+iV requires exactly 3 realm/d. We study the algebraic complexity of several other operations from the repertoire of complex arithmetic. We show, for instance, that complex inversion requires exactly 4m/d and that general complex division requires at least 5m/d. For the latter problem an upperbound of 6m/d is known, leaving some speculation as to its precise complexity. The proofs illustrate several criteria which may be of more general use in assessing the complexity of concrete sets of rational functions.
Zusammenfassung
Bekanntlich erfordert die Berechung des Produkts zweier komplexer ZahlenX+iY undU+iV genau 3 reellem/d. In dieser Arbeit wird die algebraische Komplexität einiger anderer Operationen aus dem Bereich der komplexen Arithmetik untersucht. Zum Beispiel zeigen wir, daß die Inversion komplexer Zahlen genau 4 und die Division mindestens 5 reellem/d erfordert. Für das zweite Problem ist 6 als obere Schranke bekannt, so daß die genaue Komplexität der Division ein offenes Problem bleibt. Die Beweise benützen einige Kriterien, die auch allgemein für Komplexitätsbetrachtungen über fest vorgegebene Mengen rationaler Funktionen von Nutzen sein könnten.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A. V., Hopcroft, J., Ullman, J. D.: The design and analysis of computer algorithms. Reading, Mass.: Addison-Wesley 1974.
Alt, H., van Leeuwen, J.: A classroom note on computing products in finite-dimensional algebras. EATCS Bulletin, number 8, June 1979, pp. 14–17.
Alt, H., van Leeuwen, J.: The complexity of complex division (extended abstract), in: Conference record of the 2nd Int. Conference on Fundamentals of Computation Theory, Berlin/Wendisch-Rietz (DDR), September 17–21, 1979 (to appear).
Borodin, A., Munro, I.: The computational complexity of algebraic and numeric problems. (Theory of Comput. Series, Vol. 1.) New York: American Elsevier 1975.
Fiduccia, C. M., Zalcstein, Y.: Algebras having linear multiplicative complexities. J. ACM24, 311–331 (1977).
Fiduccia, C. M.: Remarks on a note of Alt and van Leeuwen regarding products in finite-dimensional algebras. EATCS Bulletin, number 9, October 1979, pp. 32–33.
Kung, H. T.: The computational complexity of algebraic numbers, Proc. 5th Annual ACM Symp. on Theory of Computing, 1973, pp. 334–342.
Munro, I.: Some results concerning efficient and optimal algorithms, Proc. 3rd Annual ACM Symp. on Theory of Computing, 1971, pp. 40–44.
Smith, R. L., Algorithm 116: Complex division, CACM5, 435 (1962).
Strassen, V.: Evaluation of rational functions, in: Complexity of computer computations (Miller, R. E., Thatcher, J. W., eds.), pp. 1–10. New York: Plenum Press 1972.
Strassen, V.: Vermeidung von Divisionen. J. für die Reine u. Angew. Mathematik264, 184–202 (1973).
van Leeuwen, J., van Emde Boas, P.: Some elementary proofs of lower bounds in complexity theory. Linear Alg. and its Appl.19, 63–80 (1978).
Winograd, S.: On the number of multiplications necessary to compute certain functions. Comm. Pure and Appl. Math.23, 165–179 (1970).
Winograd, S.: On the multiplication of 2×2 matrices. Linear Alg. and its Appl.4, 381–388 (1971).
Winograd, S.: The effect of the field of constants on the number of multiplications, Conf. Record 16th Annual IEEE Symp. on Foundations of Computer Science, Berkeley, 1975, pp. 1–2.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Alt, H., van Leeuwen, J. The complexity of basic complex operations. Computing 27, 205–215 (1981). https://doi.org/10.1007/BF02237978
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02237978