Regeneration homotopies for solving systems of polynomials
HTML articles powered by AMS MathViewer
- by Jonathan D. Hauenstein, Andrew J. Sommese and Charles W. Wampler PDF
- Math. Comp. 80 (2011), 345-377 Request permission
Abstract:
We present a new technique, based on polynomial continuation, for solving systems of $n$ polynomials in $N$ complex variables. The method allows equations to be introduced one-by-one or in groups, obtaining at each stage a representation of the solution set that can be extended to the next stage until finally obtaining the solution set for the entire system. At any stage where positive dimensional solution components must be found, they are sliced down to isolated points by the introduction of hyperplanes. By moving these hyperplanes, one may build up the solution set to an intermediate system in which a union of hyperplanes “regenerates” the intersection of the component with the variety of the polynomial (or system of polynomials) brought in at the next stage. The theory underlying the approach guarantees that homotopy paths lead to all isolated solutions, and this capability can be used to generate witness supersets for solution components at any dimension, the first step in computing an irreducible decomposition of the solution set of a system of polynomial equations. The method is illustrated on several challenging problems, where it proves advantageous over both the polyhedral homotopy method and the diagonal equation-by-equation method, formerly the two leading approaches to solving sparse polynomial systems by numerical continuation.References
- 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
- 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
- D.J. Bates, J.D. Hauenstein, A.J. Sommese, and C.W. Wampler, Bertini: Software for Numerical Algebraic Geometry. Available at www.nd.edu/$\sim$sommese/bertini.
- Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler II, Adaptive multiprecision path tracking, SIAM J. Numer. Anal. 46 (2008), no. 2, 722–746. MR 2383209, DOI 10.1137/060658862
- Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler II, Stepsize control for path tracking, Interactions of classical and numerical algebraic geometry, Contemp. Math., vol. 496, Amer. Math. Soc., Providence, RI, 2009, pp. 21–31. MR 2555948, DOI 10.1090/conm/496/09717
- Mauro C. Beltrametti and Andrew J. Sommese, The adjunction theory of complex projective varieties, De Gruyter Expositions in Mathematics, vol. 16, Walter de Gruyter & Co., Berlin, 1995. MR 1318687, DOI 10.1515/9783110871746
- 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
- William Fulton, Intersection theory, 2nd ed., Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 2, Springer-Verlag, Berlin, 1998. MR 1644323, DOI 10.1007/978-1-4612-1700-8
- Birkett Huber and Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), no. 212, 1541–1555. MR 1297471, DOI 10.1090/S0025-5718-1995-1297471-4
- G. Lecerf, Quadratic Newton iteration for systems with multiplicity, Found. Comput. Math. 2 (2002), no. 3, 247–293. MR 1907381, DOI 10.1007/s102080010026
- Anton Leykin, Numerical primary decomposition, ISSAC 2008, ACM, New York, 2008, pp. 165–172. MR 2513502, DOI 10.1145/1390768.1390793
- 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}
- T.-L. Lee, T.Y. Li, and C.-H. Tsai, HOM4PS-2.0, Solving Polynomial Systems by the Polyhedral Homotopy Method. Software available at www.math.msu.edu/$\sim$li.
- T. Y. Li, Numerical solution of polynomial systems by homotopy continuation methods, Handbook of numerical analysis, Vol. XI, Handb. Numer. Anal., XI, North-Holland, Amsterdam, 2003, pp. 209–304. MR 2009773
- A.J. Lotka, Undamped oscillations derived from the laws of mass action, J. Amer. Chem. Soc. 42 (1920), pp. 1595–1599.
- Alexander P. Morgan, A transformation to avoid solutions at infinity for polynomial systems, Appl. Math. Comput. 18 (1986), no. 1, 77–86. MR 815773, DOI 10.1016/0096-3003(86)90029-9
- Alexander Morgan and Andrew Sommese, A homotopy for solving general polynomial systems that respects $m$-homogeneous structures, Appl. Math. Comput. 24 (1987), no. 2, 101–113. MR 914806, DOI 10.1016/0096-3003(87)90063-4
- Alexander P. Morgan and Andrew J. Sommese, Coefficient-parameter polynomial continuation, Appl. Math. Comput. 29 (1989), no. 2, 123–160. MR 977815, DOI 10.1016/0096-3003(89)90099-4
- Alexander P. Morgan, Andrew J. Sommese, and Charles W. Wampler, A product-decomposition bound for Bezout numbers, SIAM J. Numer. Anal. 32 (1995), no. 4, 1308–1325. MR 1342295, DOI 10.1137/0732061
- David Mumford, Algebraic geometry. I, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Complex projective varieties; Reprint of the 1976 edition. MR 1344216
- 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
- Takeo Ojika, Satoshi Watanabe, and Taketomo Mitsui, Deflation algorithm for the multiple roots of a system of nonlinear equations, J. Math. Anal. Appl. 96 (1983), no. 2, 463–479. MR 719330, DOI 10.1016/0022-247X(83)90055-0
- B. Roth and F. Freudenstein, Synthesis of Path-Generating Mechanisms by Numerical Methods, ASME J. Engrg. Industry, 85B(3) (1963), pp. 298–306.
- Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, Numerical decomposition of the solution sets of polynomial systems into irreducible components, SIAM J. Numer. Anal. 38 (2001), no. 6, 2022–2046. MR 1856241, DOI 10.1137/S0036142900372549
- A. J. Sommese, J. Verschelde, and C. W. Wampler, Using monodromy to decompose solution sets of polynomial systems into irreducible components, Applications of algebraic geometry to coding theory, physics and computation (Eilat, 2001) NATO Sci. Ser. II Math. Phys. Chem., vol. 36, Kluwer Acad. Publ., Dordrecht, 2001, pp. 297–315. MR 1866906
- Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, Symmetric functions applied to decomposing solution sets of polynomial systems, SIAM J. Numer. Anal. 40 (2002), no. 6, 2026–2046 (2003). MR 1974173, DOI 10.1137/S0036142901397101
- Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, Numerical irreducible decomposition using PHCpack, Algebra, geometry, and software systems, Springer, Berlin, 2003, pp. 109–129. MR 2011756
- Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, Homotopies for intersecting solution components of polynomial systems, SIAM J. Numer. Anal. 42 (2004), no. 4, 1552–1571. MR 2114290, DOI 10.1137/S0036142903430463
- Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, An intrinsic homotopy for intersecting algebraic varieties, J. Complexity 21 (2005), no. 4, 593–608. MR 2152724, DOI 10.1016/j.jco.2004.09.007
- Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, Solving polynomial systems equation by equation, Algorithms in algebraic geometry, IMA Vol. Math. Appl., vol. 146, Springer, New York, 2008, pp. 133–152. MR 2397941, DOI 10.1007/978-0-387-75155-9_{8}
- Andrew J. Sommese and Charles W. Wampler, Numerical algebraic geometry, The mathematics of numerical analysis (Park City, UT, 1995) Lectures in Appl. Math., vol. 32, Amer. Math. Soc., Providence, RI, 1996, pp. 749–763. MR 1421365
- Andrew J. Sommese and Charles W. Wampler II, The numerical solution of systems of polynomials, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. Arising in engineering and science. MR 2160078, DOI 10.1142/9789812567727
- J. Verschelde, Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Software 25(2) (1999), pp. 251–276. Software available at www.math.uic.edu/$\sim$jan.
- Jan Verschelde and Ronald Cools, Symbolic homotopy construction, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 3, 169–183. MR 1226323, DOI 10.1007/BF01202036
- Jan Verschelde, Pierre Verlinden, and Ronald Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal. 31 (1994), no. 3, 915–930. MR 1275120, DOI 10.1137/0731049
- V. Volterra, Variazionie fluttuazioni del numero d’individui in specie animali convivent, Mem. Acad. Lincei., 2 (1926), pp. 31–113.
- C. W. Wampler and A. P. Morgan, Solving the kinematics of general 6R manipulators using polynomial continuation, Robotics: applied mathematics and computational aspects (Loughborough, 1989) Inst. Math. Appl. Conf. Ser. New Ser., vol. 41, Oxford Univ. Press, New York, 1993, pp. 57–69. MR 1250881
- C.W. Wampler, A. Morgan, and A.J. Sommese, Complete solution of the nine-point path synthesis problem for four-bar linkages, ASME J. Mech. Des. 114(1) (1992), pp. 153–159.
- Bo Yu and Bo Dong, A hybrid polynomial system solving method for mixed trigonometric polynomial systems, SIAM J. Numer. Anal. 46 (2008), no. 3, 1503–1518. MR 2391004, DOI 10.1137/070681740
- Zhonggang Zeng, The closedness subspace method for computing the multiplicity structure of a polynomial system, Interactions of classical and numerical algebraic geometry, Contemp. Math., vol. 496, Amer. Math. Soc., Providence, RI, 2009, pp. 347–362. MR 2555964, DOI 10.1090/conm/496/09733
Additional Information
- Jonathan D. Hauenstein
- Affiliation: Department of Mathematics, Mailstop 3368, Texas A&M University, College Station, Texas 77843
- MR Author ID: 832839
- ORCID: 0000-0002-9252-8210
- Email: jhauenst@math.tamu.edu
- Andrew J. Sommese
- Affiliation: Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, Indiana 46556
- Email: sommese@nd.edu
- Charles W. Wampler
- Affiliation: General Motors Research and Development, Mail Code 480-106-359, 30500 Mound Road, Warren, Michigan 48090
- Email: charles.w.wampler@gm.com
- Received by editor(s): September 23, 2008
- Received by editor(s) in revised form: July 24, 2009, and October 27, 2009
- Published electronically: June 9, 2010
- Additional Notes: The first author was supported by the Duncan Chair of the University of Notre Dame, the University of Notre Dame Center for Applied Mathematics, NSF Grant DMS-0410047, NSF Grant DMS-0712910, and the Fields Institute.
The second author was supported by the Duncan Chair of the University of Notre Dame, NSF Grant DMS-0410047, and NSF Grant DMS-0712910.
The third author was supported by NSF Grant DMS-0410047 and NSF Grant DMS-0712910. - © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 80 (2011), 345-377
- MSC (2010): Primary 65H10; Secondary 13P05, 14Q99, 68W30
- DOI: https://doi.org/10.1090/S0025-5718-2010-02399-3
- MathSciNet review: 2728983