Certifying Simple Zeros of Over-Determined Polynomial Systems

1. Akogul, T.A., Hauenstein, J.D., Szanto, A.: Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\), 12 August 2014. arXiv: 1408.2721v1 [cs.SC]

2. Allamigeon, X., Gaubert, S., Magron, V., Werner, B.: Formal proofs for nonlinear optimization (2014). arXiv:1404.7282

3. Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer, New York (1998)

   Book  MATH  Google Scholar 

4. Dayton, B., Li, T., Zeng, Z.: Multiple zeros of nonlinear systems. Math. Comp. 80, 2143–2168 (2011)

   Article  MathSciNet  MATH  Google Scholar 

5. Dayton, B., Zeng, Z.: Computing the multiplicity structure in solving polynomial systems. In: Kauers, M. (ed.) Proceedings of ISSAC 2005, pp. 116–123. ACM, New York (2005)

   Google Scholar 

6. Giusti, M., Lecerf, G., Salvy, B., Yakoubsohn, J.C.: On location and approximation of clusters of zeros: case of embedding dimension one. Found. Comput. Math. 7, 1–58 (2007)

   Article  MathSciNet  MATH  Google Scholar 

7. Dedieu, J.P., Shub, M.: Newton’s method for overdetermined systems of equations. Math. Comput. 69(231), 1099–1115 (1999)

   Article  MathSciNet  MATH  Google Scholar 

8. Hauenstein, J.D., Wampler, C.W.: Isosingular sets and deflation. Found. Comput. Math. 13(3), 371–403 (2013)

   Article  MathSciNet  MATH  Google Scholar 

9. Hauenstein, J.D., Mourrain, B., Szanto, A.: Certifying isolated singular points and their multiplicity structure. In: Proceedings of ISSAC 2015, pp. 213–220 (2015)

   Google Scholar 

10. Hauenstein, J.D., Sottile, F.: Algorithm 921: alphaCertified: certifying solutions to polynomial systems. ACM Trans. Math. Softw. 38(4), 28 (2012)

    Article  MathSciNet  MATH  Google Scholar 

11. Kanzawa, Y., Kashiwagi, M., Oishi, S.: An algorithm for finding all solutions of parameter-dependent nonlinear equations with guaranteed accuracy. Electron. Commun. Jpn. (Part III: Fundam. Electron. Sci.) 82(10), 33–39 (1999)

    Article  Google Scholar 

12. Kanzawa, Y., Oishi, S.: Approximate singular solutions of nonlinear equations and a numerical method of proving their existence. Sūrikaisekikenkyūsho Kōkyūroku 990, 216–223 (1997). Theory and application of numerical calculation in science and technology, II (Japanese) Kyoto (1996)

    MathSciNet  MATH  Google Scholar 

13. Kaltofen, E., Li, B., Yang, Z., Zhi, L.: Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars. In: Proceedings of ISSAC 2008, pp. 155–164, New York. ACM (2008)

    Google Scholar 

14. Rohn, J.: Positive definiteness and stability of interval matrices. SIAM J. Matrix Anal. Appl. 15, 175–184 (1994)

    Article  MathSciNet  MATH  Google Scholar 

15. Kaltofen, E.L., Li, B., Yang, Z., Zhi, L.: Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients. J. Symb. Comput. 47(1), 1–15 (2012)

    Article  MathSciNet  MATH  Google Scholar 

16. Krawczyk, R.: Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken. Computing 4, 247–293 (1969)

    MathSciNet  MATH  Google Scholar 

17. Leykin, A., Verschelde, J., Zhao, A.: Newton’s method with deflation for isolated singularities of polynomial systems. Theor. Comput. Sci. 359, 111–122 (2006)

    Article  MathSciNet  MATH  Google Scholar 

18. Li, N., Zhi, L.: Verified error bounds for isolated singular solutions of polynomial systems. SIAM J. Numer. Anal. 52(4), 1623–1640 (2014)

    Article  MathSciNet  MATH  Google Scholar 

19. Li, S.: Linear Algebra. Higher Education Press (2006). ISBN 978-7-04-019870-6

    Google Scholar 

20. Moore, R.E.: A test for existence of solutions to nonlinear systems. SIAM J. Numer. Anal. 14, 611–615 (1977)

    Article  MathSciNet  MATH  Google Scholar 

21. Mantzaflaris, A., Mourrain, B.: Deflation and certified isolation of singular zeros of polynomial systems. In: Proceedings ISSAC 2011, pp. 249–256 (2011)

    Google Scholar 

22. Monniaux, D., Corbineau, P.: On the generation of positivstellensatz witnesses in degenerate cases. In: Eekelen, M., Geuvers, H., Schmaltz, J., Wiedijk, F. (eds.) ITP 2011. LNCS, vol. 6898, pp. 249–264. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22863-6_19

    Chapter  Google Scholar 

23. Nakaya, Y., Oishi, S., Kashiwagi, M., Kanzawa, Y.: Numerical verification of nonexistence of solutions for separable nonlinear equations and its application to all solutions algorithm. Electron. Commun. Jpn. (Part III: Fundam. Electron. Sci.) 86(5), 45–53 (2003)

    Article  Google Scholar 

24. Ojika, T.: A numerical method for branch points of a system of nonlinear algebraic equations. Appl. Numer. Math. 4, 419–430 (1988)

    Article  MathSciNet  MATH  Google Scholar 

25. Ojika, T., Watanabe, S., Mitsui, T.: Deflation algorithm for the multiple roots of a system of nonlinear equations. J. Math. Anal. Appl. 96, 463–479 (1983)

    Article  MathSciNet  MATH  Google Scholar 

26. Peyrl, H., Parrilo, P.A.: A Macaulay2 package for computing sum of squares decompositions of polynomials with rational coefficients. In: Proceeding of SNC 2007, pp. 207–208 (2007)

    Google Scholar 

27. Peyrl, H., Parrilo, P.A.: Computing sum of squares decompositions with rational coefficients. Theor. Comput. Sci. 409(2), 269–281 (2008)

    Article  MathSciNet  MATH  Google Scholar 

28. Rump, S.M.: Solving algebraic problems with high accuracy. In: Proceedings of the Symposium on A New Approach to Scientific Computation, San Diego, CA, USA, pp. 51–120. Academic Press Professional Inc. (1983)

    Google Scholar 

29. Rump, S.M., Graillat, S.: Verified error bounds for multiple roots of systems of nonlinear equations. Numer. Algorithms 54(3), 359–377 (2010)

    Article  MathSciNet  MATH  Google Scholar 

30. El Din, M.S., Zhi, L.: Computing rational points in convex semialgebraic sets and sum of squares decompositions. SIAM J. Optim. 20(6), 2876–2889 (2010)

    Article  MathSciNet  MATH  Google Scholar 

31. Smale, S.: Newton’s method estimates from data at one point. In: Ewing, R.E., Gross, K.I., Martin, C.F. (eds.) The Merging of Disciplines : New Directions in Pure, Applied and Computational Mathematics, pp. 185–196. Springer, Heidelberg (1986). doi:10.1007/978-1-4612-4984-9_13

    Chapter  Google Scholar 

32. Yamamura, K., Kawata, H., Tokue, A.: Interval solution of nonlinear equations using linear programming. BIT Numer. Math. 38(1), 186–199 (1998)

    Article  MathSciNet  MATH  Google Scholar 

33. Zeng, Z.: Computing multiple roots of inexact polynomials. Math. Comput. 74, 869–903 (2005)

    Article  MathSciNet  MATH  Google Scholar 

Download references