Complete numerical isolation of real zeros in zero-dimensional triangular systems

ABSTRACT

We present a complete numerical algorithm of isolating all the real zeros of a zero-dimensional triangular polynomial system F_n Z[x₁…,x_n]. Our system F_n is general, with no further assumptions. In particular, our algorithm successfully treat multiple zeros directly in such systems. A key idea is to introduce evaluation bounds and sleeve bounds. We implemented our algorithm and promising experimental results are shown.

REFERENCES

• 1: Alkiviadis G. Akritas, A new method for polynomial real root isolation, Proceedings of the 16th annual Southeast regional conference, p.39-43, April 13-15, 1978, Atlanta, Georgia [doi>10.1145/503643.503653]
• 2: A. Akritas , A. Strzeboński , P. Vigklas, Implementations of a New Theorem for Computing Bounds for Positive Roots of Polynomials, Computing, v.78 n.4, p.355-367, December 2006 [doi>10.1007/s00607-006-0186-y]
• 3: Eugene L. Allgower , Kurt Georg , Rick Miranda, The method of resultants for computing real solutions of polynomial systems, SIAM Journal on Numerical Analysis, v.29 n.3, p.831-844, June 1992 [doi>10.1137/0729051]
• 4: D. S. Arnon, G. E. Collins, and S. McCallum, Cylindrical algebraic decomposition. QECAD*, Springer, Wien, 136--151, 1998
• 5: Philippe Aubry , Daniel Lazard , Marc Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation, v.28 n.1-2, p.105-124, July/Aug. 1999 [doi>10.1006/jsco.1999.0269]
• 6: Richard P. Brent, Fast Multiple-Precision Evaluation of Elementary Functions, Journal of the ACM (JACM), v.23 n.2, p.242-251, April 1976 [doi>10.1145/321941.321944]
• 7: B. Buchberger, An algorithm for ?nding a basis for the residue class of zero-dimension polynomial idea. Aequationes Math, 374--383, 1970.
• 8: J. S. Cheng, X. S. Gao, and M. Li, Determine the topology of real algebraic surfaces. Mathematics of Surfaces XI, LNCS3604, Springer, 121--146, 2005.
• 9: 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]
• 10: George E. Collins , Jeremy R. Johnson , Werner Krandick, Interval arithmetic in cylindrical algebraic decomposition, Journal of Symbolic Computation, v.34 n.2, p.145-157, August 2002 [doi>10.1006/jsco.2002.0547]
• 11: Z. Du, V. Sharma, and C. K. Yap, Amortized bound for root isolation via Sturm sequences. in Proc. SNC '05, 81--93, 2005.
• 12: A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt, and N. Wolpert, A descartes algorithm for polynomials with bit stream coefficients. CASC 2005, LNCS 3718, Springer, 138--149, 2005.
• 13: L. González-Vega, T. Recio, H. Lombardi and M. F. Roy, Sturm-Habicht sequences, determinants and real roots of univariate polynomials. QECAD*, Springer, Wien, 300--316, 1998
• 14: H. Hong and V. Stahl. Safe start region by ?xed points and tightening. Computing, 53(3-4):323--335, 1994.
• 15: J. R. Johnson, Algorithms for polynomial real root isolation. QECAD*, Springer, Wien, 269--299, 1998.
• 16: D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, v.13 n.2, p.117-131, Feb. 1992 [doi>10.1016/S0747-7171(08)80086-7]
• 17: Z. Lu, B. He, Y. Luo and L. Pan, An algorithm of real root isolation for polynomial systems. Proc. SNC'05, 94--107, 2005.
• 18: B. Mourrain, Computing the isolated roots by matrix methods, Journal of Symbolic Computation, v.26 n.6, p.715-738, Dec. 1998 [doi>10.1006/jsco.1998.0236]
• 19: Renaud Rioboo, Real algebraic closure of an ordered field: implementation in Axiom, Papers from the international symposium on Symbolic and algebraic computation, p.206-215, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143312]
• 20: F. Rouillier. Solving zero-dimensional systems through the rational univariate representation. AAECC, 9:433--461, 1999.
• 21: 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]
• 22: C. B. Soh and C. S. Berger, Strict a periodic-property of polynomials with perturbed coefficients. IEEE T AC, 34:546--548, 1989.
• 23: J. Uspensky, Theory of Equations, McGraw-Hill Book Company, New York, 1948.
• 24: D. K. Wang, Zero Decomposition for System of Polynomial Equations. Proc. ASCM 2000:67--70.
• 25: D. M. Wang. Elimination Methods. Springer, Wein, New York, 2000.
• 26: W. T. Wu, Mathematics Mechanization, Science Press/Kluwer, Beijing, 2000.
• 27: Bican Xia , Lu Yang, An algorithm for isolating the real solutions of semi-algebraic systems, Journal of Symbolic Computation, v.34 n.5, p.461-477, November 2002 [doi>10.1006/jsco.2002.0572]
• 28: Chee Keng Yap, Fundamental problems of algorithmic algebra, Oxford University Press, Inc., New York, NY, 1999
• 29: Chee K. Yap, Complete subdivision algorithms, I: intersection of Bezier curves, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137890]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations

General Terms:
Algorithms, Theory

Keywords:
evaluation bound, real zero isolation, sleeve bound, triangular system