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