## Multiple zeros of nonlinear systems

HTML articles powered by AMS MathViewer

- by Barry H. Dayton, Tien-Yien Li and Zhonggang Zeng PDF
- Math. Comp.
**80**(2011), 2143-2168 Request permission

## 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.

## References

- 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**, DOI 10.1016/j.jco.2006.04.003 - 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**, DOI 10.1137/08073264X - Shui Nee Chow and Jack K. Hale,
*Methods of bifurcation theory*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 251, Springer-Verlag, New York-Berlin, 1982. MR**660633**, DOI 10.1007/978-1-4613-8159-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** - 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 - James W. Demmel,
*Applied numerical linear algebra*, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR**1463942**, DOI 10.1137/1.9781611971446 - Jacques Emsalem,
*Géométrie des points épais*, Bull. Soc. Math. France**106**(1978), no. 4, 399–416 (French, with English summary). MR**518046**, DOI 10.24033/bsmf.1879 - 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**, DOI 10.1007/978-3-662-02421-8 - 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** - Wolfgang Gröbner,
*Algebraische Geometrie. $2$. Teil: Arithmetische Theorie der Polynomringe*, B. I. Hochschultaschenbücher, vol. 737/737, Bibliographisches Institut, Mannheim-Vienna-Zurich, 1970 (German). MR**0330161** - Gert-Martin Greuel and Gerhard Pfister,
*A*, 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**Singular**introduction to commutative algebra**2363237** - G.-M. Greuel, G. Pfister, and H. Schönemann,
*Singular 3.0. A Computer Algebra System for Polynomial Computations*, Centre for Computer Algebra, Univ. of Kaiserslautern, 2005. - 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**, DOI 10.1090/S0025-5718-98-00906-5 - Martin Kreuzer and Lorenzo Robbiano,
*Computational commutative algebra. 2*, Springer-Verlag, Berlin, 2005. MR**2159476** - 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**, DOI 10.1016/j.jmaa.2007.05.049 - E. Lasker,
*Zur Theorie der moduln und Ideale*, Math. Ann.**60**(1905), no. 1, 20–116 (German). MR**1511288**, DOI 10.1007/BF01447495 - 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} - 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** - 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**, DOI 10.1137/S0895479803435282 - 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** - 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**, DOI 10.1090/S0002-9947-96-01671-6 - 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**, DOI 10.1017/CBO9781107340954 - 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 - 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**, DOI 10.1006/jcom.2000.0554 - Richard P. Stanley,
*Hilbert functions of graded algebras*, Advances in Math.**28**(1978), no. 1, 57–83. MR**485835**, DOI 10.1016/0001-8708(78)90045-2 - 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**, DOI 10.1145/281508.281525 - Hans J. Stetter,
*Numerical polynomial algebra*, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2004. MR**2048781**, DOI 10.1137/1.9780898717976 - 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**, DOI 10.1090/gsm/046 - G. H. Thallinger,
*Analysis of Zero Clusters in Multivariate Polynomial Systems*, Diploma Thesis, Tech. Univ. Vienna, 1996. - Xiaoli Wu and Lihong Zhi,
*Computing the multiplicity structure from geometric involutive form*, ISSAC 2008, ACM, New York, 2008, pp. 325–332. MR**2513521**, DOI 10.1145/1390768.1390812 - 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**, DOI 10.1007/978-3-662-29244-0 - Zhonggang Zeng,
*Computing multiple roots of inexact polynomials*, Math. Comp.**74**(2005), no. 250, 869–903. MR**2114653**, DOI 10.1090/S0025-5718-04-01692-8 - —,
*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. - —,
*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.

## Additional Information

**Barry H. Dayton**- Affiliation: Department of Mathematics, Northeastern Illinois University, Chicago, Illinois 60625
- Email: bhdayton@neiu.edu
**Tien-Yien Li**- Affiliation: Department of Mathematics, Michigan State University, East Lansing, Michigan 48824
- Email: li@math.msu.edu
**Zhonggang Zeng**- Affiliation: Department of Mathematics, Northeastern Illinois University, Chicago, Illinois 60625
- MR Author ID: 214819
- ORCID: 0000-0001-8879-8077
- Email: zzeng@neiu.edu
- Received by editor(s): September 26, 2009
- Received by editor(s) in revised form: June 24, 2010
- Published electronically: February 3, 2011
- Additional Notes: The second author’s research was supported in part by NSF under Grant DMS-0811172.

The third author’s research was supported in part by NSF under Grant DMS-0715127. - © Copyright 2011
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**80**(2011), 2143-2168 - MSC (2010): Primary 65H10; Secondary 68W30
- DOI: https://doi.org/10.1090/S0025-5718-2011-02462-2
- MathSciNet review: 2813352