Abstract
Existing algorithms for isolating real solutions of zero-dimensional polynomial systems do not compute the multiplicities of the solutions. In this paper, we define in a natural way the multiplicity of solutions of zero-dimensional triangular polynomial systems and prove that our definition is equivalent to the classical definition of local (intersection) multiplicity. Then we present an effective and complete algorithm for isolating real solutions with multiplicities of zero-dimensional triangular polynomial systems using our definition. The algorithm is based on interval arithmetic and square-free factorization of polynomials with real algebraic coefficients. The computational results on some examples from the literature are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Collins G E, Akritas A G. Polynomial real root isolation using Descartes’ rule of signs. In: Jenks R D, ed. Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computations, Yorktown Heights, NY, USA, 1976. 272–275
Collins G E. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Brakhage H, ed. Automata Theory and Formal Languages, LNCS Vol 33. Berlin: Springer, 1975. 134–165
Collins G E, Loos R. Real zeros of polynomials. In: Buchberger B, Collins G E, Loos R, eds. Computer Algebra: Symbolic and Algebraic Computation. New York: Springer, 1982. 83–94
Akritas A G, Bocharov A V, Strzeboński A W. Implementation of real root isolation algorithms in Mathematica. In: Abstracts of the International Conference on Interval and Computer-Algebraic Methods in Science and Engineering, St. Petersburg, Russia, 1994. 23–27
Johnson J R. Algorithms for polynomial real root isolation. In: Caviness B F, Johnson J R, eds. Quantifier Elimination and Cylinderical Algebraic Decomposition. New York: Springer-Verlag, 1998. 269–299
Rouillier F, Zimmermann P. Efficient isolation of polynomial’s real roots. J Comput Appl Math, 2004, 162: 33–50
Sharma V. Complexity of real root isolation using continued fractions. In: Brown C W, ed. Proc ISSAC’07, Waterloo, Canada, 2007. 339–346
**a B, Yang L. An algorithm for isolating the real solutions of semi-algebraic systems. J Symb Comput, 2002, 34: 461–477
**a B, Zhang T. Real solution isolation using interval arithmetic. Comput Math Appl, 2006, 52: 853–860
Cheng J S, Gao X S, Yap C K. Complete numerical isolation of real zeros in general triangular systems. In: Brown C W, ed. Proc ISSAC’07, Waterloo, Canada, 2007. 92–99
Cox D, Little J, O’shea D. Using Algebraic Geometry. 1st ed. New York: Springer, 1998. 130–178
Greuel G M, Pfister G. A Singular Introduction to Commutative Algebra. 1st ed. Berlin: Springer-Verlag, 2002. 1–88
Wang D. Elimination Methods. 1st ed. New York: Springer, 2001. 220–226
**a B, Hou X R. A complete algorithm for counting real solutions of polynomial systems of equations and inequalities. Comput Math Appl, 2002, 44: 633–642
Geddes K O, Czapor S R, Labahn G. Algorithms for Computer Algebra. 1st ed. Boston: Kluwer, 1992. 337–347
Gathen J, Gerhard J. Modern Computer Algebra. 1st ed. Cambridge: Cambridge University Press, 1999. 369–373
**a B. DISCOVERER: A tool for solving semi-algebraic systems. ACM SIGSAM Bull, 2007, 41: 102–103
Dayton B H, Zeng Z G. Computing the multiplicity structure in solving polynomial systems. In: Brown C W, ed. Proc ISSAC’05, Bei**g, China, 2005. 116–123
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, Z., Fang, T. & **a, B. Real solution isolation with multiplicity of zero-dimensional triangular systems. Sci. China Inf. Sci. 54, 60–69 (2011). https://doi.org/10.1007/s11432-010-4154-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-010-4154-y