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
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.
- 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.
Retrieve articles in Mathematics of Computation with MSC (2010): 65H10, 68W30
Retrieve articles in all journals with MSC (2010): 65H10, 68W30
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.
Article copyright:
© Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.