On isolation of simple multiple zeros and clusters of zeros of polynomial systems

Hao, Zhiwei; Jiang, Wenrong; Li, Nan; Zhi, Lihong

doi:10.1090/mcom/3479

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