On isolation of simple multiple zeros and clusters of zeros of polynomial systems
HTML articles powered by AMS MathViewer
- by Zhiwei Hao, Wenrong Jiang, Nan Li and Lihong Zhi HTML | PDF
- Math. Comp. 89 (2020), 879-909 Request permission
Abstract:
Given a well-constrained polynomial system $f$ associated with a simple multiple zero $x$ of multiplicity $\mu$, we give a computable separation bound for isolating $x$ from the other zeros of $f$. When $x$ is only given with a limited accuracy, we give a numerical criterion for isolating a nearby cluster of $\mu$ zeros of $f$ (counting multiplicities) in a ball around $x$.References
- Tulay Ayyildiz Akoglu, Jonathan D. Hauenstein, and Agnes Szanto, Certifying solutions to overdetermined and singular polynomial systems over $\Bbb {Q}$, J. Symbolic Comput. 84 (2018), 147–171. MR 3673011, DOI 10.1016/j.jsc.2017.03.004
- Carlos A. Berenstein, Roger Gay, Alekos Vidras, and Alain Yger, Residue currents and Bezout identities, Progress in Mathematics, vol. 114, Birkhäuser Verlag, Basel, 1993. MR 1249478, DOI 10.1007/978-3-0348-8560-7
- Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636, DOI 10.1007/978-1-4612-0701-6
- Barry H. Dayton, Tien-Yien Li, and Zhonggang Zeng, Multiple zeros of nonlinear systems, Math. Comp. 80 (2011), no. 276, 2143–2168. MR 2813352, DOI 10.1090/S0025-5718-2011-02462-2
- Barry H. Dayton and Zhonggang Zeng, Computing the multiplicity structure in solving polynomial systems, ISSAC’05, ACM, New York, 2005, pp. 116–123. MR 2280537, DOI 10.1145/1073884.1073902
- D. W. Decker, H. B. Keller, and C. T. Kelley, Convergence rates for Newton’s method at singular points, SIAM J. Numer. Anal. 20 (1983), no. 2, 296–314. MR 694520, DOI 10.1137/0720020
- D. W. Decker and C. T. Kelley, Newton’s method at singular points. I, SIAM J. Numer. Anal. 17 (1980), no. 1, 66–70. MR 559463, DOI 10.1137/0717009
- D. W. Decker and C. T. Kelley, Newton’s method at singular points. II, SIAM J. Numer. Anal. 17 (1980), no. 3, 465–471. MR 581492, DOI 10.1137/0717039
- D. W. Decker and C. T. Kelley, Convergence acceleration for Newton’s method at singular points, SIAM J. Numer. Anal. 19 (1982), no. 1, 219–229. MR 646604, DOI 10.1137/0719012
- Jean-Pierre Dedieu and Mike Shub, On simple double zeros and badly conditioned zeros of analytic functions of $n$ variables, Math. Comp. 70 (2001), no. 233, 319–327. MR 1680867, DOI 10.1090/S0025-5718-00-01194-7
- Jianwei Dian and R. Baker Kearfott, Existence verification for singular and nonsmooth zeros of real nonlinear systems, Math. Comp. 72 (2003), no. 242, 757–766. MR 1954966, DOI 10.1090/S0025-5718-02-01427-8
- Ioannis Z. Emiris, Bernard Mourrain, and Elias P. Tsigaridas, The DMM bound: multivariate (aggregate) separation bounds, ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2010, pp. 243–250. MR 2920560, DOI 10.1145/1837934.1837981
- Shmuel Friedland and Lek-Heng Lim, Nuclear norm of higher-order tensors, Math. Comp. 87 (2018), no. 311, 1255–1281. MR 3766387, DOI 10.1090/mcom/3239
- M. Giusti, G. Lecerf, B. Salvy, and J.-C. Yakoubsohn, On location and approximation of clusters of zeros of analytic functions, Found. Comput. Math. 5 (2005), no. 3, 257–311. MR 2168678, DOI 10.1007/s10208-004-0144-z
- M. Giusti, G. Lecerf, B. Salvy, and J.-C. Yakoubsohn, On location and approximation of clusters of zeros: case of embedding dimension one, Found. Comput. Math. 7 (2007), no. 1, 1–49. MR 2283341, DOI 10.1007/s10208-004-0159-5
- Marc Giusti and Jean-Claude Yakoubsohn, Numerical approximation of multiple isolated roots of analytic systems. Manuscript available at https://arxiv.org/abs/1707.06301, 2017.
- A. Griewank, On solving nonlinear equations with simple singularities or nearly singular solutions, SIAM Rev. 27 (1985), no. 4, 537–563. MR 812453, DOI 10.1137/1027141
- Andreas Griewank and M. R. Osborne, Newton’s method for singular problems when the dimension of the null space is $>1$, SIAM J. Numer. Anal. 18 (1981), no. 1, 145–149. MR 603436, DOI 10.1137/0718011
- Zhiwei Hao, Wenlong Jiang, Nan Li, and Lihong Zhi, Computing simple multiple zeros of polynomial systems. Manuscript available at https://www.arxiv.org/pdf/1703.03981.pdf, 2017.
- Jonathan D. Hauenstein, Bernard Mourrain, and Agnes Szanto, Certifying isolated singular points and their multiplicity structure, ISSAC’15—Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2015, pp. 213–220. MR 3388302
- Jonathan D. Hauenstein, Bernard Mourrain, and Agnes Szanto, On deflation and multiplicity structure, J. Symbolic Comput. 83 (2017), 228–253. MR 3645652, DOI 10.1016/j.jsc.2016.11.013
- Christopher J. Hillar and Lek-Heng Lim, Most tensor problems are NP-hard, J. ACM 60 (2013), no. 6, Art. 45, 39. MR 3144915, DOI 10.1145/2512329
- Erich L. Kaltofen, Bin Li, Zhengfeng Yang, and Lihong Zhi, Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, J. Symbolic Comput. 47 (2012), no. 1, 1–15. MR 2854844, DOI 10.1016/j.jsc.2011.08.002
- Yuchi Kanzawa and Shin’ichi Oishi, Imperfect singular solutions of nonlinear equations and a numerical method of proving their existence, IEICE Transactions on Fundamentals of Electronics, Communications and Computer sciences, 82(6):1062–1069, 1999.
- R. Baker Kearfott and Jianwei Dian, Existence verification for higher degree singular zeros of nonlinear systems, SIAM J. Numer. Anal. 41 (2003), no. 6, 2350–2373. MR 2034619, DOI 10.1137/S0036142901386057
- R. Baker Kearfott, Jianwei Dian, and A. Neumaier, Existence verification for singular zeros of complex nonlinear systems, SIAM J. Numer. Anal. 38 (2000), no. 2, 360–379. MR 1770053, DOI 10.1137/S0036142999361074
- G. Lecerf, Quadratic Newton iteration for systems with multiplicity, Found. Comput. Math. 2 (2002), no. 3, 247–293. MR 1907381, DOI 10.1007/s102080010026
- Anton Leykin, Jan Verschelde, and Ailing Zhao, Newton’s method with deflation for isolated singularities of polynomial systems, Theoret. Comput. Sci. 359 (2006), no. 1-3, 111–122. MR 2251604, DOI 10.1016/j.tcs.2006.02.018
- Anton Leykin, Jan Verschelde, and Ailing Zhao, Higher-order deflation for polynomial systems with isolated singular solutions, Algorithms in algebraic geometry, IMA Vol. Math. Appl., vol. 146, Springer, New York, 2008, pp. 79–97. MR 2397938, DOI 10.1007/978-0-387-75155-9_{5}
- Nan Li and Lihong Zhi, Computing the multiplicity structure of an isolated singular solution: case of breadth one, J. Symbolic Comput. 47 (2012), no. 6, 700–710. MR 2908589, DOI 10.1016/j.jsc.2011.12.027
- Nan Li and Lihong Zhi, Computing isolated singular solutions of polynomial systems: case of breadth one, SIAM J. Numer. Anal. 50 (2012), no. 1, 354–372. MR 2888317, DOI 10.1137/110827247
- Nan Li and Lihong Zhi, Verified error bounds for isolated singular solutions of polynomial systems: case of breadth one, Theoret. Comput. Sci. 479 (2013), 163–173. MR 3034563, DOI 10.1016/j.tcs.2012.10.028
- Nan Li and Lihong Zhi, Verified error bounds for isolated singular solutions of polynomial systems, SIAM J. Numer. Anal. 52 (2014), no. 4, 1623–1640. MR 3229659, DOI 10.1137/120902914
- Angelos Mantzaflaris and Bernard Mourrain, Deflation and certified isolation of singular zeros of polynomial systems, ISSAC 2011—Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2011, pp. 249–256. MR 2895219, DOI 10.1145/1993886.1993925
- Maria Grazia Marinari, Teo Mora, and Hans Michael Möller, Gröbner duality and multiplicities in polynomial system solving, in Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, ISSAC ’95, pages 167–179, New York, NY, USA, 1995. ACM.
- B. Mourrain, Isolated points, duality and residues, J. Pure Appl. Algebra 117/118 (1997), 469–493. Algorithms for algebra (Eindhoven, 1996). MR 1457851, DOI 10.1016/S0022-4049(97)00023-6
- Takeo Ojika, Modified deflation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations, J. Math. Anal. Appl. 123 (1987), no. 1, 199–221. MR 881541, DOI 10.1016/0022-247X(87)90304-0
- Takeo Ojika, A numerical method for branch points of a system of nonlinear algebraic equations, Appl. Numer. Math. 4 (1988), no. 5, 419–430. MR 948507, DOI 10.1016/0168-9274(88)90018-9
- Takeo Ojika, Satoshi Watanabe, and Taketomo Mitsui, Deflation algorithm for the multiple roots of a system of nonlinear equations, J. Math. Anal. Appl. 96 (1983), no. 2, 463–479. MR 719330, DOI 10.1016/0022-247X(83)90055-0
- L. B. Rall, Convergence of the Newton process to multiple solutions, Numer. Math. 9 (1966), 23–37. MR 210316, DOI 10.1007/BF02165226
- G. W. Reddien, On Newton’s method for singular problems, SIAM J. Numer. Anal. 15 (1978), no. 5, 993–996. MR 507559, DOI 10.1137/0715064
- G. W. Reddien, Newton’s method and high order singularities, Comput. Math. Appl. 5 (1979), no. 2, 79–86. MR 539566, DOI 10.1016/0898-1221(79)90061-0
- Siegfried M. Rump and Stef Graillat, Verified error bounds for multiple roots of systems of nonlinear equations, Numer. Algorithms 54 (2010), no. 3, 359–377. MR 2661328, DOI 10.1007/s11075-009-9339-3
- Yun-Qiu Shen and Tjalling J. Ypma, Newton’s method for singular nonlinear equations using approximate left and right nullspaces of the Jacobian, Appl. Numer. Math. 54 (2005), no. 2, 256–265. MR 2148044, DOI 10.1016/j.apnum.2004.09.029
- Yun-Qiu Shen and Tjalling J. Ypma, Solving rank-deficient separable nonlinear equations, Appl. Numer. Math. 57 (2007), no. 5-7, 609–615. MR 2322434, DOI 10.1016/j.apnum.2006.07.025
- Michael Shub and Steve Smale, Complexity of Bezout’s theorem. IV. Probability of success; extensions, SIAM J. Numer. Anal. 33 (1996), no. 1, 128–148. MR 1377247, DOI 10.1137/0733008
- Mike Shub and Steven Smale, Computational complexity. On the geometry of polynomials and a theory of cost. I, Ann. Sci. École Norm. Sup. (4) 18 (1985), no. 1, 107–142. MR 803197
- M. Shub and S. Smale, Computational complexity: on the geometry of polynomials and a theory of cost. II, SIAM J. Comput. 15 (1986), no. 1, 145–161. MR 822199, DOI 10.1137/0215011
- Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, DOI 10.1090/S0273-0979-1981-14858-8
- Steve Smale, Newton’s method estimates from data at one point, The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985) Springer, New York, 1986, pp. 185–196. MR 870648
- Hans J. Stetter, Numerical polynomial algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2004. MR 2048781, DOI 10.1137/1.9780898717976
- Jean-Claude Yakoubsohn, Finding a cluster of zeros of univariate polynomials, J. Complexity 16 (2000), no. 3, 603–638. Complexity theory, real machines, and homotopy (Oxford, 1999). MR 1787887, DOI 10.1006/jcom.2000.0555
- Jean-Claude Yakoubsohn, Simultaneous computation of all the zero-clusters of a univariate polynomial, Foundations of computational mathematics (Hong Kong, 2000) World Sci. Publ., River Edge, NJ, 2002, pp. 433–455. MR 2021992
- Norio Yamamoto, Regularization of solutions of nonlinear equations with singular Jacobian matrices, J. Inform. Process. 7 (1984), no. 1, 16–21. MR 760383
Additional Information
- Zhiwei Hao
- Affiliation: Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; and University of Chinese Academy of Sciences, Beijing 100049, China
- MR Author ID: 1203148
- Email: haozhiwei@mmrc.iss.ac.cn
- Wenrong Jiang
- Affiliation: Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, and China; University of Chinese Academy of Sciences, Beijing 100049, China
- Email: jiangwr@amss.ac.cn
- Nan Li
- Affiliation: College of Mathematics and Statistics, Shenzhen University, Shenzhen 518060, China
- MR Author ID: 968435
- Email: nan.li@szu.edu.cn
- Lihong Zhi
- Affiliation: Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; and University of Chinese Academy of Sciences, Beijing 100049, China
- MR Author ID: 615840
- Email: lzhi@mmrc.iss.ac.cn
- Received by editor(s): August 20, 2018
- Received by editor(s) in revised form: February 21, 2019, and May 6, 2019
- Published electronically: October 1, 2019
- Additional Notes: This work was carried out when the third author was with Tianjin University. This work was supported in part by the National Key Research Project of China 2018YFA0306702 (Zhi) and the National Natural Science Foundation of China 11571350 (Zhi), 11601378 (Li)
The third author is the corresponding author. - © Copyright 2019 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 879-909
- MSC (2010): Primary 65H10, 74G35, 68W30, 32-04, 32S99
- DOI: https://doi.org/10.1090/mcom/3479
- MathSciNet review: 4044454