Multiple zeros of nonlinear systems

Dayton, Barry; Li, Tien-Yien; Zeng, Zhonggang

doi:10.1090/S0025-5718-2011-02462-2

Multiple zeros of nonlinear systems

Authors: Barry H. Dayton, Tien-Yien Li and Zhonggang Zeng
Journal: Math. Comp. 80 (2011), 2143-2168
MSC (2010): Primary 65H10; Secondary 68W30
DOI: https://doi.org/10.1090/S0025-5718-2011-02462-2
Published electronically: February 3, 2011
MathSciNet review: 2813352
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: As an attempt to bridge between numerical analysis and algebraic geometry, this paper formulates the multiplicity for the general nonlinear system at an isolated zero, presents an algorithm for computing the multiplicity structure, proposes a depth-deflation method for accurate computation of multiple zeros, and introduces the basic algebraic theory of the multiplicity.

Furthermore, this paper elaborates and proves some fundamental properties of the multiplicity, including local finiteness, consistency, perturbation invariance, and depth-deflatability.

As a justification of this formulation, the multiplicity is proved to be consistent with the multiplicity defined in algebraic geometry for the special case of polynomial systems.

The proposed algorithms can accurately compute the multiplicity and the multiple zeros using floating point arithmetic even if the nonlinear system is perturbed.

1. Dan Bates, Chris Peterson, and Andrew J. Sommese, A numerical-symbolic algorithm for computing the multiplicity of a component of an algebraic set, J. Complexity 22 (2006), no. 4, 475–489. MR 2246892, https://doi.org/10.1016/j.jco.2006.04.003
2. Daniel J. Bates, Jonathan D. Hauenstein, Chris Peterson, and Andrew J. Sommese, A numerical local dimensions test for points on the solution set of a system of polynomial equations, SIAM J. Numer. Anal. 47 (2009), no. 5, 3608–3623. MR 2576513, https://doi.org/10.1137/08073264X
3. Shui Nee Chow and Jack K. Hale, Methods of bifurcation theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Science], vol. 251, Springer-Verlag, New York-Berlin, 1982. MR 660633
4. David A. Cox, John Little, and Donal O’Shea, Using algebraic geometry, 2nd ed., Graduate Texts in Mathematics, vol. 185, Springer, New York, 2005. MR 2122859
5. 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, https://doi.org/10.1145/1073884.1073902
6. James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942
7. Jacques Emsalem, Géométrie des points épais, Bull. Soc. Math. France 106 (1978), no. 4, 399–416 (French, with English summary). MR 518046
8. William Fulton, Intersection theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 2, Springer-Verlag, Berlin, 1984. MR 732620
9. Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
10. Wolfgang Gröbner, Algebraische Geometrie. 2. Teil: Arithmetische Theorie der Polynomringe, Bibliographisches Institut, Mannheim-Vienna-Zurich, 1970 (German). B. I. Hochschultaschenbücher, 737/737a*. MR 0330161
11. Gert-Martin Greuel and Gerhard Pfister, A Singular introduction to commutative algebra, Second, extended edition, Springer, Berlin, 2008. With contributions by Olaf Bachmann, Christoph Lossen and Hans Schönemann; With 1 CD-ROM (Windows, Macintosh and UNIX). MR 2363237
12. G.-M. GREUEL, G. PFISTER, AND H. SCH¨ONEMANN, Singular 3.0. A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, Univ. of Kaiserslautern, 2005.
13. Hidetsune Kobayashi, Hideo Suzuki, and Yoshihiko Sakai, Numerical calculation of the multiplicity of a solution to algebraic equations, Math. Comp. 67 (1998), no. 221, 257–270. MR 1434942, https://doi.org/10.1090/S0025-5718-98-00906-5
14. Martin Kreuzer and Lorenzo Robbiano, Computational commutative algebra. 2, Springer-Verlag, Berlin, 2005. MR 2159476
15. Y. C. Kuo and T. Y. Li, Determining dimension of the solution component that contains a computed zero of a polynomial system, J. Math. Anal. Appl. 338 (2008), no. 2, 840–851. MR 2386465, https://doi.org/10.1016/j.jmaa.2007.05.049
16. E. Lasker, Zur Theorie der moduln und Ideale, Math. Ann. 60 (1905), no. 1, 20–116 (German). MR 1511288, https://doi.org/10.1007/BF01447495
17. 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, https://doi.org/10.1016/j.tcs.2006.02.018
18. 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, https://doi.org/10.1007/978-0-387-75155-9_5
19. Bang-He Li, A method to solve algebraic equations up to multiplicities via Ritt-Wu’s characteristic sets, Acta Anal. Funct. Appl. 5 (2003), no. 2, 97–109 (English, with English and Chinese summaries). MR 1992681
20. T. Y. Li and Zhonggang Zeng, A rank-revealing method with updating, downdating, and applications, SIAM J. Matrix Anal. Appl. 26 (2005), no. 4, 918–946. MR 2178205, https://doi.org/10.1137/S0895479803435282
21. F. S. Macaulay, The algebraic theory of modular systems, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1994. Revised reprint of the 1916 original; With an introduction by Paul Roberts. MR 1281612
22. M. G. Marinari, H. M. Möller, and T. Mora, On multiplicities in polynomial system solving, Trans. Amer. Math. Soc. 348 (1996), no. 8, 3283–3321. MR 1360228, https://doi.org/10.1090/S0002-9947-96-01671-6
23. Teo Mora, Solving polynomial equation systems. II, Encyclopedia of Mathematics and its Applications, vol. 99, Cambridge University Press, Cambridge, 2005. Macaulay’s paradigm and Gröbner technology. MR 2164357
24. B. Mourrain, Isolated points, duality and residues, J. Pure Appl. Algebra 117/118 (1997), 469–493. Algorithms for algebra (Eindhoven, 1996). MR 1457851, https://doi.org/10.1016/S0022-4049(97)00023-6
25. 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, https://doi.org/10.1016/0022-247X(87)90304-0
26. Andrew J. Sommese and Jan Verschelde, Numerical homotopies to compute generic points on positive dimensional algebraic sets, J. Complexity 16 (2000), no. 3, 572–602. Complexity theory, real machines, and homotopy (Oxford, 1999). MR 1787886, https://doi.org/10.1006/jcom.2000.0554
27. Richard P. Stanley, Hilbert functions of graded algebras, Advances in Math. 28 (1978), no. 1, 57–83. MR 485835, https://doi.org/10.1016/0001-8708(78)90045-2
28. Hans J. Stetter and Günther H. Thallinger, Singular systems of polynomials, Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (Rostock), ACM, New York, 1998, pp. 9–16. MR 1805166, https://doi.org/10.1145/281508.281525
29. Hans J. Stetter, Numerical polynomial algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2004. MR 2048781
30. Joseph L. Taylor, Several complex variables with connections to algebraic geometry and Lie groups, Graduate Studies in Mathematics, vol. 46, American Mathematical Society, Providence, RI, 2002. MR 1900941
31. G. H. THALLINGER, Analysis of Zero Clusters in Multivariate Polynomial Systems, Diploma Thesis, Tech. Univ. Vienna, 1996.
32. Xiaoli Wu and Lihong Zhi, Computing the multiplicity structure from geometric involutive form, ISSAC 2008, ACM, New York, 2008, pp. 325–332. MR 2513521, https://doi.org/10.1145/1390768.1390812
33. Oscar Zariski and Pierre Samuel, Commutative algebra. Vol. II, The University Series in Higher Mathematics, D. Van Nostrand Co., Inc., Princeton, N. J.-Toronto-London-New York, 1960. MR 0120249
34. Zhonggang Zeng, Computing multiple roots of inexact polynomials, Math. Comp. 74 (2005), no. 250, 869–903. MR 2114653, https://doi.org/10.1090/S0025-5718-04-01692-8
35. -, ApaTools: A Maple and Matlab toolbox for approximate polynomial algebra, in Software for Algebraic Geometry, IMA Volume 148, M. Stillman, N. Takayama, and J. Verschelde, eds., Springer, 2008, pp.149-167.
36. -, The closedness subspace method for computing the multiplicity structure of a polynomial system.
to appear: Interactions between Classical and Numerical Algebraic Geometry, Contemporary Mathematics series, American Mathematical Society, 2009.