Almost tight recursion tree bounds for the Descartes method

ABSTRACT

We give a unified ("basis free") framework for the Descartes method for real root isolation of square-free real polynomials. This framework encompasses the usual Descartes' rule of sign method for polynomials in the power basis as well as its analog in the Bernstein basis. We then give a new bound on the size of the recursion tree in the Descartes method for polynomials with real coefficients. Applied to polynomials A(X) = Εⁿ_i=0 a_iXⁱ with integer coefficients |a_i| < 2^L, this yields a bound of O(n(L + logn)) on the size of recursion trees. We show that this bound is tight for L = Ω(logn), and we use it to derive the best known bit complexity bound for the integer case.

REFERENCES

• 1: S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Springer, 2003.
• 2: P. Batra. Abschätzungen und Iterationsverfahren für Polynom-Nullstellen. PhD thesis, Technical University Hamburg-Harburg, 1999.
• 3: 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]
• 4: G. E. Collins , J. R. Johnson, Quantifier elimination and the sign variation method for real root isolation, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.264-271, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74574]
• 5: J. H. Davenport. Computer algebra for cylindrical algebraic decomposition. Tech. Rep., Royal Inst. of Technology, Dept. of Numer. Analysis and Computing Science, Stockholm, Sweden, 1985. Reprinted as Tech. Rep. 88-10, U. of Bath, School of Math. Sciences, Bath, England. http://www.bath.ac.uk/~masjhd/TRITA.pdf.
• 6: Z. Du, V. Sharma, and C. K. Yap. Amortized bound for root isolation via Sturm sequences. In D. Wang and L. Zhi, editors, Proc. Internat. Workshop on Symbolic-Numeric Computation, pages 81--93, 2005. Int'l Workshop on Symbolic Numeric Computation, Xi'an, China, Jul 19--21, 2005.
• 7: I. Z. Emiris, B. Mourrain, and E. P. Tsigaridas. Real algebraic numbers: Complexity analysis and experimentations. Research Report 5897, INRIA, April 2006. http://www.inria.fr/rrrt/rr-5897.html.
• 8: C. G. J. Jacobi. Observatiunculae ad theoriam aequationum pertinentes. Journal für die reine und angewandte Mathematik, 13:340--352, 1835. Available from http://gdz.sub.uni-goettingen.de.
• 9: J. R. Johnson. Algorithms for polynomial real root isolation. In B. F. Caviness and J. R. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, pages 269--299. Springer, 1998.
• 10: Jeremy R. Johnson , Werner Krandick , Anatole D. Ruslanov, Architecture-aware classical Taylor shift by 1, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.200-207, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073913]
• 11: W. Krandick. Isolierung reeller Nullstellen von Polynomen. In J. Herzberger, editor, Wissenschaftliches Rechnen, pages 105--154. Akademie-Verlag, Berlin, 1995.
• 12: W. Krandick and K. Mehlhorn. New bounds for the Descartes method. J. Symbolic Computation, 41(1):49--66, 2006.
• 13: J. M. Lane and R. F. Riesenfeld. Bounds on a polynomial. BIT, 21:112--117, 1981.
• 14: Sylvester—Habicht sequences and fast Cauchy index computation, Journal of Symbolic Computation, v.31 n.3, p.315-341, March 2001 [doi>10.1006/jsco.2000.0427 ]
• 15: K. Mahler. An inequality for the discriminant of a polynomial. Michigan Mathematical Journal, 11:257--262, 1964.
• 16: Maurice Mignotte, Some inequalities about univariate polynomials, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.195-199, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806395]
• 17: M. Mignotte. On the distance between the roots of a polynomial. Applicable Algebra in Engineering, Commun., and Comput., 6:327--332, 1995.
• 18: M. Mignotte and D. Ştefǎnescu. Polynomials: An Algorithmic Approach. Springer, Singapore, 1999.
• 19: B. Mourrain, F. Rouillier, and M.-F. Roy. The Bernstein basis and real root isolation. In J. E. Goodman, J. Pach, and E. Welzl, editors, Combinatorial and Computational Geometry, number 52 in MSRI Publications, pages 459--478. Cambridge University Press, 2005.
• 20: B. Mourrain , M. N. Vrahatis , J. C. Yakoubsohn, On the complexity of isolating real roots and computing with certainty the topological degree, Journal of Complexity, v.18 n.2, p.612-640, June 2002 [doi>10.1006/jcom.2001.0636]
• 21: A. M. Ostrowski. Note on Vincent's theorem. Annals of Mathematics, 2nd Ser., 52:702--707, 1950. Reprinted in: A. Ostrowski, Collected Mathematical Papers, vol. 1, 728--733, Birkhäuser, 1983.
• 22: Hartmut Prautzsch , Wolfgang Boehm , Marco Paluszny, Bezier and B-Spline Techniques, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 23: Daniel Reischert, Asymptotically fast computation of subresultants, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.233-240, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258792]
• 24: F. Rouillier and P. Zimmermann. Efficient isolation of a polynomial{'s} real roots. Rapport de Recherche 4113, INRIA, 2001. http://www.inria.fr/rrrt/rr-4113.html.
• 25: Fabrice Rouillier , Paul Zimmermann, Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics, v.162 n.1, p.33-50, 1 January 2004 [doi>10.1016/j.cam.2003.08.015]
• 26: Joachim von zur Gathen , Jürgen Gerhard, Fast algorithms for Taylor shifts and certain difference equations, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.40-47, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258745]
• 27: Chee Keng Yap, Fundamental problems of algorithmic algebra, Oxford University Press, Inc., New York, NY, 1999

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

General Terms:
Algorithms, Theory

Keywords:
Bernstein basis, Davenport-Mahler bound, Descartes method, Descartes rule of signs, polynomial real root isolation