[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2465506.2465951acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
research-article

Verified error bounds for real solutions of positive-dimensional polynomial systems

Published: 26 June 2013 Publication History

Abstract

In this paper, we propose two algorithms for verifying the existence of real solutions of positive-dimensional polynomial systems. The first one is based on the critical point method and the homotopy continuation method. It targets for verifying the existence of real roots on each connected component of an algebraic variety VRn defined by polynomial equations. The second one is based on the low-rank moment matrix completion method and aims for verifying the existence of at least one real roots on VRn. Combined both algorithms with the verification algorithms for zero-dimensional polynomial systems, we are able to find verified real solutions of positive-dimensional polynomial systems very efficiently for a large set of examples.

References

[1]
Aubry, P., Rouillier, F., and Safey El Din, M. Real solving for positive dimensional systems. J. Symb. Comput. 34, 6 (2002), 543--560.
[2]
Bank, B., Giusti, M., Heintz, J., Lehmann, L., and Pardo, L. M. Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces. Foundations of Computational Mathematics 12 (2012), 75--122.
[3]
Bank, B., Giusti, M., Heintz, J., and Mbakop, G. M. Polar varieties and efficient real elimination. MATHEMATISCHE ZEITSCHRIFT 238 (2000), 2001.
[4]
Bank, B., Giusti, M., Heintz, J., Safey El Din, M., and Schost, E. On the geometry of polar varieties. Applicable Algebra in Engineering, Communication and Computing 21 (2010), 33--83.
[5]
Basu, S., Pollack, R., and Roy, M.-F. On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43, 6 (Nov. 1996), 1002--1045.
[6]
Beltrán, C., and Leykin, A. Certified Numerical Homotopy Tracking. Experimental Mathematics 21 (2012), 69--83.
[7]
Camilla, M. H., and Ragni, P. Polars of real singular plane curves. In Alorithm in Algebraic Geometry (2008), Springer, pp. 99--115.
[8]
Canny, J. Computing roadmaps of general semi-algebraic sets. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, H. Mattson, T. Mora, and T. Rao, Eds., vol. 539 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 1991, pp. 94--107.
[9]
Chen, X., Frommer, A., and Lang, B. Computational existence proofs for spherical t-designs. Numerische Mathematik 117 (2011), 289--305.
[10]
Chen, X., and Womersley, R. S. Existence of solutions to systems of underdetermined equations and spherical designs. SIAM J. NUMER. ANAL. 44, 6 (2006), 2326--2341.
[11]
Chesi, G., Garulli, A., Tesi, A., and Vicino, A. Characterizing the solution set of polynomial systems in terms of homogeneous forms: an LMI approach. International Journal of Robust and Nonlinear Control 13, 13 (2003), 1239--1257.
[12]
Collins, G. Quantifier elimination for real closed fields by cylindrical algebraic decompostion. vol. 33 of Lecture Notes in Computer Science. 1975, pp. 134--183.
[13]
Everett, H., Lazard, S., Lazard, D., and Safey El Din, M. The voronoi diagram of three lines. In Proceedings of the twenty-third annual symposium on Computational geometry (2007), SCG '07, ACM, pp. 255--264.
[14]
Greuet, A., and Safey El Din, M. Deciding reachability of the infimum of a multivariate polynomial. In Proceedings of the 36th international symposium on Symbolic and algebraic computation (New York, NY, USA, 2011), ISSAC '11, ACM, pp. 131--138.
[15]
Grigorév, D., and Vorobjov, N.N., J. Counting connected components of a semialgebraic set in subexponential time. computational complexity 2 (1992), 133--186.
[16]
Grigorév, D. Y., and Jr, N. V. Solving systems of polynomial inequalities in subexponential time. Journal of Symbolic Computation 5, 1 lC2 (1988), 37--64.
[17]
Hauenstein, J. D. Numerically computing real points on algebraic sets. ArXiv e-prints (May 2011).
[18]
Hauenstein, J. D., and Sottile, F. Algorithm 921: alphacertified: Certifying solutions to polynomial systems. ACM Trans. Math. Softw. 38, 4 (Aug. 2012), 28:1--28:20.
[19]
Heintz, J., Roy, M.-F., and Solern Ãş, P. Description of the connected components of a semialgebraic set in single exponential time. Discrete & Computational Geometry 11 (1994), 121--140.
[20]
Henrion, D., and Lasserre, J. Detecting global optimality and extracting solutions in GloptiPoly. In Positive polynomials in control, vol. 312 of Lecture Notes in Control and Inform. Sci. Springer, Berlin, 2005, pp. 293--310.
[21]
Krawczyk, R. Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken. Computing (1969), 187--201.
[22]
Lasserre, J. Moments, Positive Polynomials and Their Applications. Imperial College Press, 2009.
[23]
Lasserre, J., Laurent, M., and Rostalski, P. Semidefinite characterization and computation of zero-dimensional real radical ideals. Foundations of Computational Mathematics 8 (2008), 607--647.
[24]
Lee, T.-L., Li, T.-Y., and Tsai, C.-H. Hom4ps-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method. Computing 83, 2-3 (2008), 109--133.
[25]
Leykin, A., Verschelde, J., and Zhao, A. Newton's method with deflation for isolated singularities of polynomial systems. Theoretical Computer Science 359, 1 (2006), 111--122.
[26]
Li, N., and Zhi, L. Verified error bounds for isolated singular solutions of polynomial systems. Preprint, arxiv.org/pdf/1201.3443.
[27]
Li, N., and Zhi, L. Verified error bounds for isolated singular solutions of polynomial systems: case of breadth one. To appear in Theoretical Computer Science.
[28]
Ma, Y., and Zhi. Computing real solutions of polynomial systems via low-rank moment matrix completion. In ISSAC (2012), ACM, pp. 249--256.
[29]
Mantzaflaris, A., and Mourrain, B. Deflation and certified isolation of singular zeros of polynomial systems. In Proceedings of the 36th international symposium on Symbolic and algebraic computation (New York, NY, USA, 2011), A. Leykin, Ed., ISSAC '11, ACM, pp. 249--256.
[30]
Moore, R. E. A test for existence of solutions to nonlinear systems. SIAM Journal on Numerical Analysis 14, 4 (1977), pp. 611--615.
[31]
Renegar, J. On the computational complexity and geometry of the first-order theory of the reals. part i: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of Symbolic Computation 13, 3 (1992), 255--299.
[32]
Rouillier, F. Efficient algorithms based on critical points method. In Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science (2001), S. Basu and L. Gonzlclez-Vega, Eds., American Mathematical Society, pp. 123--138.
[33]
Rouillier, F., Roy, M.-F., and Safey El Din, M. Finding at least one point in each connected component of a real algebraic set defined by a single equation. J. Complexity 16, 4 (2000), 7160--750.
[34]
Rump, S. Solving algebraic problems with high accuracy. In Proc. of the symposium on A new approach to scientific computation (San Diego, CA, USA, 1983), Academic Press Professional, Inc., pp. 51--120.
[35]
Rump, S. INTLAB - INTerval LABoratory. In Developments in Reliable Computing (1999), T. Csendes, Ed., Kluwer Academic Publishers, Dordrecht, pp. 77--104.
[36]
Rump, S., and Graillat, S. Verified error bounds for multiple roots of systems of nonlinear equations. Numerical Algorithms 54, 3 (2009), 359--377.
[37]
Safey El Din, M., and Schost, E. Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In ISSAC (2003), ACM, pp. 224--231.
[38]
Seidenberg, A. A new decision method for elementary algebra. Annals Math. 60 (1954), 365--374.
[39]
Shen, F., Wu, W., and Xia, B. Real Root Isolation of Polynomial Equations Based on Hybrid Computation. ArXiv e-prints, July 2012.
[40]
Sommese, A. J., and Verschelde, J. Numerical homotopies to compute generic points on positive dimensional algebraic sets. J. Complex. 16, 3 (Sept. 2000), 572--602.
[41]
Sommese, A. J., and Wampler, C. W. Numerical algebraic geometry. In The mathematics of numerical analysis (Park City, UT, 1995) (1996), S. S. J. Renegar, M. Shub, Ed., Lectures in Appl. Math.,32, Amer. Math. Soc., Providence, RI, pp. 749--763.
[42]
Sommese, A. J., and Wampler, C. W. The numerical solution of systems of polynomials - arising in engineering and science. World Scientific, 2005.
[43]
Spang, S. J. On the computation of the real radical. Thesis, Technische Universität Kaiserslautern, 2007.
[44]
Stetter, H. Numerical Polynomial Algebra. SIAM, 2004.
[45]
Verschelde, J. Algorithm 795: Phcpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. 25, 2 (1999), 251--276.

Cited By

View all
  • (2024)Unlabeled Sensing Using Rank-One Moment Matrix CompletionProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669674(46-55)Online publication date: 16-Jul-2024
  • (2023)VerifyRealRoots: A Matlab Package for Computing Verified Real Solutions of Polynomials Systems of Equations and InequalitiesJournal of Systems Science and Complexity10.1007/s11424-023-1406-736:2(866-883)Online publication date: 18-Feb-2023
  • (2023)Solving SMT over Non-linear Real Arithmetic via Numerical Sampling and Symbolic VerificationDependable Software Engineering. Theories, Tools, and Applications10.1007/978-981-99-8664-4_10(171-188)Online publication date: 15-Dec-2023
  • Show More Cited By

Index Terms

  1. Verified error bounds for real solutions of positive-dimensional polynomial systems

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation
    June 2013
    400 pages
    ISBN:9781450320597
    DOI:10.1145/2465506
    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: 26 June 2013

    Permissions

    Request permissions for this article.

    Check for updates

    Qualifiers

    • Research-article

    Conference

    ISSAC'13
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 395 of 838 submissions, 47%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 28 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Unlabeled Sensing Using Rank-One Moment Matrix CompletionProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669674(46-55)Online publication date: 16-Jul-2024
    • (2023)VerifyRealRoots: A Matlab Package for Computing Verified Real Solutions of Polynomials Systems of Equations and InequalitiesJournal of Systems Science and Complexity10.1007/s11424-023-1406-736:2(866-883)Online publication date: 18-Feb-2023
    • (2023)Solving SMT over Non-linear Real Arithmetic via Numerical Sampling and Symbolic VerificationDependable Software Engineering. Theories, Tools, and Applications10.1007/978-981-99-8664-4_10(171-188)Online publication date: 15-Dec-2023
    • (2017)Penalty Function Based Critical Point Approach to Compute Real Witness Solution Points of Polynomial SystemsComputer Algebra in Scientific Computing10.1007/978-3-319-66320-3_27(377-391)Online publication date: 30-Aug-2017
    • (2017)The Convergence Conditions of Interval Newton’s Method Based on Point EstimatesComputer Algebra in Scientific Computing10.1007/978-3-319-66320-3_20(272-284)Online publication date: 30-Aug-2017
    • (2014)Numerical and geometric properties of a method for finding points on real solution componentsProceedings of the 2014 Symposium on Symbolic-Numeric Computation10.1145/2631948.2631969(111-117)Online publication date: 28-Jul-2014
    • (2014)Symbolic-numeric algorithms for computing validated resultsProceedings of the 39th International Symposium on Symbolic and Algebraic Computation10.1145/2608628.2627491(25-26)Online publication date: 23-Jul-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

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media