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.

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 https://doi.org/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 https://doi.org/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
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 https://doi.org/10.1145/1073884.1073902
James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942
Jacques Emsalem, Géométrie des points épais, Bull. Soc. Math. France 106 (1978), no. 4, 399–416 (French, with English summary). MR 518046
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
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, Bibliographisches Institut, Mannheim-Vienna-Zurich, 1970 (German). B. I. Hochschultaschenbücher, 737/737a$^{\ast }$. MR 0330161
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

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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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

B. Mourrain, Isolated points, duality and residues, J. Pure Appl. Algebra 117/118 (1997), 469–493. Algorithms for algebra (Eindhoven, 1996). MR 1457851, DOI https://doi.org/10.1016/S0022-4049%2897%2900023-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 https://doi.org/10.1016/0022-247X%2887%2990304-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 https://doi.org/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 https://doi.org/10.1016/0001-8708%2878%2990045-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 https://doi.org/10.1145/281508.281525

Hans J. Stetter, Numerical polynomial algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2004. MR 2048781

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

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 https://doi.org/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

Zhonggang Zeng, Computing multiple roots of inexact polynomials, Math. Comp. 74 (2005), no. 250, 869–903. MR 2114653, DOI https://doi.org/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.