Regeneration homotopies for solving systems of polynomials

Authors:
Jonathan D. Hauenstein, Andrew J. Sommese and Charles W. Wampler

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

Published electronically:
June 9, 2010

MathSciNet review:
2728983

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new technique, based on polynomial continuation, for solving systems of polynomials in 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.

**1.**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**, https://doi.org/10.1137/08073264X**2.**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**, https://doi.org/10.1016/j.jco.2006.04.003**3.**D.J. Bates, J.D. Hauenstein, A.J. Sommese, and C.W. Wampler,

Bertini: Software for Numerical Algebraic Geometry.

Available at www.nd.edu/sommese/bertini.**4.**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**, https://doi.org/10.1137/060658862**5.**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**, https://doi.org/10.1090/conm/496/09717**6.**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****7.**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**, https://doi.org/10.1145/1073884.1073902**8.**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****9.**Birkett Huber and Bernd Sturmfels,*A polyhedral method for solving sparse polynomial systems*, Math. Comp.**64**(1995), no. 212, 1541–1555. MR**1297471**, https://doi.org/10.1090/S0025-5718-1995-1297471-4**10.**G. Lecerf,*Quadratic Newton iteration for systems with multiplicity*, Found. Comput. Math.**2**(2002), no. 3, 247–293. MR**1907381**, https://doi.org/10.1007/s102080010026**11.**Anton Leykin,*Numerical primary decomposition*, ISSAC 2008, ACM, New York, 2008, pp. 165–172. MR**2513502**, https://doi.org/10.1145/1390768.1390793**12.**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**, https://doi.org/10.1016/j.tcs.2006.02.018**13.**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**, https://doi.org/10.1007/978-0-387-75155-9_5**14.**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/li.**15.**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****16.**A.J. Lotka,

Undamped oscillations derived from the laws of mass action,*J. Amer. Chem. Soc.*42 (1920), pp. 1595-1599.**17.**Alexander P. Morgan,*A transformation to avoid solutions at infinity for polynomial systems*, Appl. Math. Comput.**18**(1986), no. 1, 77–86. MR**815773**, https://doi.org/10.1016/0096-3003(86)90029-9**18.**Alexander Morgan and Andrew Sommese,*A homotopy for solving general polynomial systems that respects 𝑚-homogeneous structures*, Appl. Math. Comput.**24**(1987), no. 2, 101–113. MR**914806**, https://doi.org/10.1016/0096-3003(87)90063-4**19.**Alexander P. Morgan and Andrew J. Sommese,*Coefficient-parameter polynomial continuation*, Appl. Math. Comput.**29**(1989), no. 2, 123–160. MR**977815**, https://doi.org/10.1016/0096-3003(89)90099-4**20.**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**, https://doi.org/10.1137/0732061**21.**David Mumford,*Algebraic geometry. I*, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Complex projective varieties; Reprint of the 1976 edition. MR**1344216****22.**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**, https://doi.org/10.1016/0022-247X(87)90304-0**23.**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**, https://doi.org/10.1016/0022-247X(83)90055-0**24.**B. Roth and F. Freudenstein,

Synthesis of Path-Generating Mechanisms by Numerical Methods,*ASME J. Engrg. Industry*, 85B(3) (1963), pp. 298-306.**25.**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**, https://doi.org/10.1137/S0036142900372549**26.**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****27.**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**, https://doi.org/10.1137/S0036142901397101**28.**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****29.**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**, https://doi.org/10.1137/S0036142903430463**30.**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**, https://doi.org/10.1016/j.jco.2004.09.007**31.**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**, https://doi.org/10.1007/978-0-387-75155-9_8**32.**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****33.**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****34.**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/jan.**35.**Jan Verschelde and Ronald Cools,*Symbolic homotopy construction*, Appl. Algebra Engrg. Comm. Comput.**4**(1993), no. 3, 169–183. MR**1226323**, https://doi.org/10.1007/BF01202036**36.**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**, https://doi.org/10.1137/0731049**37.**V. Volterra,

Variazionie fluttuazioni del numero d'individui in specie animali convivent,*Mem. Acad. Lincei.*, 2 (1926), pp. 31-113.**38.**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****39.**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.**40.**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**, https://doi.org/10.1137/070681740**41.**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**, https://doi.org/10.1090/conm/496/09733

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
65H10,
13P05,
14Q99,
68W30

Retrieve articles in all journals with MSC (2010): 65H10, 13P05, 14Q99, 68W30

Additional Information

**Jonathan D. Hauenstein**

Affiliation:
Department of Mathematics, Mailstop 3368, Texas A&M University, College Station, Texas 77843

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

DOI:
https://doi.org/10.1090/S0025-5718-2010-02399-3

Keywords:
Algebraic set,
component of solutions,
diagonal homotopy,
embedding,
equation-by-equation solver,
generic point,
homotopy continuation,
irreducible component,
numerical irreducible decomposition,
numerical algebraic geometry,
path following,
polynomial system,
witness point

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.

Article copyright:
© Copyright 2010
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.