Computing the irreducible real factors and components of an algebraicf curve

ABSTRACT

We present algorithms that decompose an algebraic curve with rational coefficients in its defining bivariate equation into its irreducible real factors and its non-empty irreducible real components. We show that our algorithms are of polynomial bit complexity in the degree of the equation and the size of its coefficients. Our construction is based on computing the irreducible complex factors and then investigating high precision complex floating point coefficients of these factors and the complex norms.

REFERENCES

• 1: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
• 2: John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
• 3: CHISTOV, A. L. and GRIGORYEV, D. Yu., "Subexponential-time solving of systems of algebraic equations I," Tech. Report E-9-83, Steklov Mathematical Institute, Leningrad, 1983.
• 4: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 5: COLLINS, G. E. and HOROWITZ, E., "The minimum root separation of a polynomial," Math. Comput. 28, pp. 589-597 (1974).
• 6: DVORNICICH, R. and TRAVERSO, C., "Newton symmetric functions and the arithmetic of algebraically closed fields," Manuscript, Univ. Pisa, June 1987.
• 7: GEBAUER, R., Personal communication, April 1986.
• 8: JACOBSON, N., Basic Algebra I; W. H. Freeman & Co., San Francisco, 1974.
• 9: KALTOFEN, E., "Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization," SIAM J. Comp. 14, pp. 469-489 (1985a).
• 10: Erich Kaltofen, Fast parallel absolute irreducibility testing, Journal of Symbolic Computation, v.1 n.1, p.57-68, March 1985 [doi>10.1016/S0747-7171(85)80029-8]
• 11: Erich Kaltofen, Deterministic irreducibility testing of polynomials over large finite fields, Journal of Symbolic Computation, v.4 n.1, p.77-82, August 1987 [doi>10.1016/S0747-7171(87)80055-X]
• 12: LANDAU, E., "Sur quelques theoremes de M. Petrovie relatifs aux zeroes des fonctions analytiques," Bull. Soc. Math. France 33, pp. 251-261 (1905).
• 13: LIPSON, J., Elements of Algebra and Algebraic Cornputing; Addison-Wesley Publ., Reading, Mass., 1981.
• 14: LOOS, R., "Computing in algebraic extensions," in Computer Algebra, 2nd ed., edited by B. Buchberger et al; Springer Verlag, Vienna, pp. 173-187, 1982.
• 15: MAHLER, K., "An inequality for the discriminant of a polynomial," Michigan Math. J. 11, pp. 257-262 (1964).
• 16: MIGNOTTE, M., "Some useful bounds," in Computer Algebra, 2nd ed., edited by B. Buchberger et al; Springer Verlag, Vienna, pp. 259-263, 1982.
• 17: RENAGAR, J., "A faster P-space algorithm for deciding the existential theory of the reals," Proc. 29th Annual Symp. Foundations of Comp. Sci., pp. 291-295 (1988).
• 18: SCHONHAGE, A., "The fundamental theorem of algebra in terms of computational complexity," Tech. Report, Univ. Tubingen, 1982.
• 19: SEIDENBERG, A., "A new decision method for elementary algebra," Annals Math. 60, pp. 365-374 (1954).
• 20: TRAGER, B. M., "Integration of algebraic functions," Ph.D. Thesis, MIT, 1984.
• 21: VAN DER WAERDEN, B. L., Modern Algebra; F. Ungar Publ. Co., New York, 1953.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory