Regeneration homotopies for solving systems of polynomials

Hauenstein, Jonathan; Sommese, Andrew; Wampler, Charles

doi:10.1090/S0025-5718-2010-02399-3

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