On the sign of a real algebraic number

ABSTRACT

In an ordered algebraic extension field of the rationales algorithms for sign determinations are studied. Two new algorithms are analyzed in detail and shown to be asymptotically and in practice faster than previous algorithms.

REFERENCES

• 1: G. E. Collins, Computer Algebra of Polynomials and Rational Functions, Amer. Math. Monthly 80, (Aug.-Sept. 1973), 725-754
• 2: C. R. Rubald, Algorithms for Polynomials over a Real Algebraic Number Field, Computer Sciences Dep., University of Wisconsin, Madison Techn. Report No. 206, Jan. 1974
• 3: H. Zassenhaus, A Real Root Calculus, Proceedings of a Conference held at Oxford, (Aug.-Sept. 1967), 383-393
• 4: Lee E. Heindel, Integer Arithmetic Algorithms for Polynomial Real Zero Determination, Journal of the ACM (JACM), v.18 n.4, p.533-548, Oct. 1971 [doi>10.1145/321662.321667]
• 5: George E. Collins , Rüdiger Loos, Polynomial real root isolation by differentiation, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.15-25, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806319]
• 6: George E. Collins , Alkiviadis G. Akritas, Polynomial real root isolation using Descarte's rule of signs, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.272-275, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806346]
• 7: R. Loos, private communication
• 8: S. Rump, Diplomarbeit, Kaiserslautern 1976
• 9: G. E. Collins, a list of SAC-I reports is contained in the KWIC-Index, SIGSAM Bulletin of the ACM, 8(1974), 17-44
• 10: 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
• 11: H. Kempfert, On Sign Determinations in Real Algebraic Numbers Fields, Num. Math. 11, (1968) 170-174
• 12: M. Mignotte, An Inequality About Factors of Polynomials, Mathematics of Computation, Vol. 28, No. 128 (October 1974), pp. 1153-1157
• 13: M. Mignotte, Sur la complexité certains algorithmes ou intervient la séparation des racines d'un polynomial
• 14: G. E. Collins and E. Horowitz, The Minimum Root Separation of a Polynomial, Math. of Comp, Vol. 28, No. 126(1974) 589-597

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

General Terms:
Algorithms