skip to main content
10.1145/1277548.1277562acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

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

Published: 29 July 2007 Publication History

Abstract

We present a complete numerical algorithm of isolating all the real zeros of a zero-dimensional triangular polynomial system Fn Z[x1…,xn]. Our system Fn 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]
A. Akritas, A new method for polynomial real root isolation. Proc. of the 16th Annual Southeast Regional Conference, 39--43, 1978.
[2]
A. Akritas, A. Strzeboński, and P. Vigklas. Implementations of a new theorem for computing bounds for positive roots of polynomials. Computing, 78(4):355--367, 2006.
[3]
E. L. Allgower, K. Georg, and R. Miranda, The method of resultants for computing real solutions of polynomial systems. SIAM Journal on Numerical Analysis, 29:831--844, 1992.
[4]
D. S. Arnon, G. E. Collins, and S. McCallum, Cylindrical algebraic decomposition. QECAD*, Springer, Wien, 136--151, 1998
[5]
P. Aubry, D. Lazard, and M. Moreno Maza. On the theories of triangular sets. JSC, 28(1-2):10--124, 1999.
[6]
R. P. Brent, Fast multiple-precision evaluation of elementary functions. JACM, 23:242--251, 1976.
[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]
G. E. Collins and A. G. Akritas. Polynomial real root isolation using Descartes' rule of signs. Proc. ISSAC'76, 272--275, 1976.
[10]
G. E. Collins, J. R. Johnson, and W. Krandick, Interval arithmetic in cylindrical algebraic decomposition. JSC, 34:145--157, 2002.
[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. 13(2):117--131, February 1992.
[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. JSC, 26:715--738, 1998.
[19]
R. Rioboo. Real algebraic closure of an ordered field, implementation in axiom. Proc. ISSAC'92:206--215, ACM Press, 1992.
[20]
F. Rouillier. Solving zero-dimensional systems through the rational univariate representation. AAECC, 9:433--461, 1999.
[21]
F. Rouillier and P. Zimmermann. Efficient isolation of polynomial real roots. J. of Comp. and App. Math., 162(1):33--50, 2003.
[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]
B. Xia and L. Yang, An algorithm for isolating the real solutions of semi-algebraic systems. JSC, 34:461--477, 2002.
[28]
C. K. Yap, Fundamental problems of algorithmic algebra, Oxford Press, 2000.
[29]
C. K. Yap, Complete subdivision algorithms, I: intersection of Bezier curves. Proc. ACM SCG'06, 217--226, 2006. *QECAD means Quantifier Elimination and Cylindrical Algebraic Decomposition. The appendix is omitted in this abstract.

Cited By

View all
  • (2019)Deciding Univariate Polynomial Problems Using Untrusted Certificates in Isabelle/HOLJournal of Automated Reasoning10.1007/s10817-017-9424-662:1(69-91)Online publication date: 1-Jan-2019
  • (2015)Separating linear forms and Rational Univariate Representations of bivariate systemsJournal of Symbolic Computation10.1016/j.jsc.2014.08.00968:P1(84-119)Online publication date: 1-May-2015
  • (2014)Cylindrical Algebraic Decomposition in the RegularChains LibraryMathematical Software – ICMS 201410.1007/978-3-662-44199-2_65(425-433)Online publication date: 2014
  • Show More Cited By

Index Terms

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

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation
    July 2007
    406 pages
    ISBN:9781595937438
    DOI:10.1145/1277548
    • General Chair:
    • Dongming Wang
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 29 July 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. evaluation bound
    2. real zero isolation
    3. sleeve bound
    4. triangular system

    Qualifiers

    • Article

    Conference

    ISSAC07
    Sponsor:
    ISSAC07: International Symposium on Symbolic and Algebraic Computation
    July 29 - August 1, 2007
    Ontario, Waterloo, Canada

    Acceptance Rates

    Overall Acceptance Rate 395 of 838 submissions, 47%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)3
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)Deciding Univariate Polynomial Problems Using Untrusted Certificates in Isabelle/HOLJournal of Automated Reasoning10.1007/s10817-017-9424-662:1(69-91)Online publication date: 1-Jan-2019
    • (2015)Separating linear forms and Rational Univariate Representations of bivariate systemsJournal of Symbolic Computation10.1016/j.jsc.2014.08.00968:P1(84-119)Online publication date: 1-May-2015
    • (2014)Cylindrical Algebraic Decomposition in the RegularChains LibraryMathematical Software – ICMS 201410.1007/978-3-662-44199-2_65(425-433)Online publication date: 2014
    • (2014)Real Root Isolation of Polynomial Equations Based on Hybrid ComputationComputer Mathematics10.1007/978-3-662-43799-5_26(375-396)Online publication date: 1-Oct-2014
    • (2013)Triangular decomposition of semi-algebraic systemsJournal of Symbolic Computation10.1016/j.jsc.2011.12.01449(3-26)Online publication date: 1-Feb-2013
    • (2013)Parallel computation of real solving bivariate polynomial systems by zero-matching methodApplied Mathematics and Computation10.1016/j.amc.2013.01.039219:14(7533-7541)Online publication date: 1-Mar-2013
    • (2011)Real solution isolation with multiplicity of zero-dimensional triangular systemsScience China Information Sciences10.1007/s11432-010-4154-y54:1(60-69)Online publication date: 10-Jan-2011
    • (2010)Triangular decomposition of semi-algebraic systemsProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1837972(187-194)Online publication date: 25-Jul-2010
    • (2009)Computing cylindrical algebraic decomposition via triangular decompositionProceedings of the 2009 international symposium on Symbolic and algebraic computation10.1145/1576702.1576718(95-102)Online publication date: 28-Jul-2009
    • (2009)Topology determination and isolation for implicit plane curvesProceedings of the 2009 ACM symposium on Applied Computing10.1145/1529282.1529534(1140-1141)Online publication date: 8-Mar-2009
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media