A new method for polynomial real root isolation

ABSTRACT

A new method is presented for the isolation of the real roots of a given integral, univariate, square-free polynomial P. This method is based on Vincent's theorem and only uses: (i) Descartes' rule of signs, and (ii) transformations of the form x = a1 + 1/x′, x′ = a2 + 1/x″, x″ = a3 + 1/x‴, ..., for positive, integral ai's. The key element in this procedure is the calculation of the quantities a1, a2, a3,... . We compute them as "positive lower root bounds" of polynomials and the resulting algorithm has the best theoretical computing time achieved thus far. Empirical results also verify the superiority of our method over all others existing.

REFERENCES

• 1: Akritas, A. G., "Vincent's Theorem in Algebraic Manipulation", Ph.D. Thesis (in preparation), North Carolina State University, 1978.
• 2: Akritas, A. G., "A Correction on a Theorem by Uspensky", submitted to the Journal of the Greek Mathematical Societw, 1978.
• 3: Akritas, A. G. and Danielopoulos, S.D., "On the Forgotten Theorem of Mr. Vincent", Historia Mathematica, to appear.
• 4: 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]
• 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: 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]
• 7: Kappos, D. A., Theory of Complex Functions, Athens, 1963 (in Greek).
• 8: Uspensky, J. V., Theory of Equations, McGraw- Hill, New York, 1948.
• 9: Vincent, "Sur la resolutions equations numeriques, Journal de Mathematiques Pures et Appliquees", Vol. 1, 1836, pp. 341-372.