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

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.**D.J. Bates, J.D. Hauenstein, C. Peterson, and A.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), pp. 3608-3623. MR**2576513****2.**D.J. Bates, C. Peterson, and A.J. Sommese,

A numerical-symbolic algorithm for computing the multiplicity of a component of an algebraic set,*J. Complexity*, 22 (2006), pp. 475-489. MR**2246892 (2007c:14067)****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.**D.J. Bates, J.D. Hauenstein, A.J. Sommese, and C.W. Wampler,

Adaptive multiprecision path tracking,*SIAM J. Numer. Anal.*, 46 (2008), pp. 722-746. MR**2383209 (2008m:65147)****5.**D.J. Bates, J.D. Hauenstein, A.J. Sommese, and C.W. Wampler,

Stepsize control for path tracking,

in*Interactions of Classical and Numerical Algebraic Geometry*, D. Bates, G. Besana, S. Di Rocco, and C. Wampler (eds.),*Contemporary Mathematics*496 (2009), 21-31. MR**2555948****6.**M. Beltrametti and A.J. Sommese,*The adjunction theory of complex projective varieties*,

Expositions in Mathematics, 16, Walter De Gruyter, Berlin, 1995. MR**1318687 (96f:14004)****7.**B. Dayton and Z. Zeng,

Computing the multiplicity structure in solving polynomial systems,

in Proceedings of ISSAC 2005, ACM, New York, 2005, pp. 116-123. MR**2280537****8.**W. Fulton,*Intersection theory*, volume 2 of*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]*,

Springer-Verlag, Berlin, second edition, 1998. MR**1644323 (99d:14003)****9.**B. Huber and B. Sturmfels,

A polyhedral method for solving sparse polynomial systems,*Math. Comp.*, 64(212) (1995), pp. 1541-1555. MR**1297471 (95m:65100)****10.**G. Lecerf,

Quadratic Newton iteration for systems with multiplicity,*Found. Comput. Math.*, 2(3) (2002), pp. 247-293. MR**1907381 (2003f:65090)****11.**A. Leykin,

Numerical primary decomposition,

in Symbolic and Algebraic Computation, Proceedings of ISSAC 2008, Linz/Hagenberg, Austria, July 20-23, 2008.

Edited by J.R. Sendra and L. González-Vega, ACM, 2008. MR**2513502****12.**A. Leykin, J. Verschelde, and A. Zhao,

Newton's method with deflation for isolated singularities of polynomial systems,*Theor. Comp. Sci.*359 (2006), pp. 111-122. MR**2251604 (2007k:65083)****13.**A. Leykin, J. Verschelde, and A. Zhao,

Higher-order deflation for polynomial systems with isolated singular solutions,

in*IMA Volume 146: Algorithms in Algebraic Geometry*, A. Dickenstein, F.-O. Schreyer, and A.J. Sommese, eds., Springer, New York, 2008, pp. 79-97. MR**2397938 (2009f:65130)****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,

in*Handbook of Numerical Analysis. Volume XI. Special Volume: Found. Comp. Math.*, edited by F. Cucker, North-Holland, 2003, pp. 209-304. MR**2009773 (2004k:65089)****16.**A.J. Lotka,

Undamped oscillations derived from the laws of mass action,*J. Amer. Chem. Soc.*42 (1920), pp. 1595-1599.**17.**A.P. Morgan,

A transformation to avoid solutions at infinity for polynomial systems,*Appl. Math. Comput.*, 18(1) (1986), pp. 77-86. MR**815773 (87c:90193)****18.**A.P. Morgan and A.J. Sommese,

A homotopy for solving general polynomial systems that respects -homogeneous structures,*Appl. Math. Comput.*, 24(2) (1987), pp. 101-113. MR**914806 (88j:65110)****19.**A.P. Morgan and A.J. Sommese,

Coefficient-parameter polynomial continuation,*Appl. Math. Comput.*, 29(2) (1989), pp. 123-160.

Errata:*Appl. Math. Comput.*, 51 (1992), p. 207. MR**977815 (90f:58018); MR 1180600****20.**A.P. Morgan, A.J. Sommese, and C.W. Wampler,

A product-decomposition bound for Bezout numbers,*SIAM J. Numer. Anal.*32(4) (1995), pp. 1308-1325. MR**1342295 (96i:65040)****21.**D. Mumford,*Algebraic geometry I: Complex projective varieties*,

Classics in Mathematics, Springer-Verlag, Berlin, 1995, Reprint of the 1976 edition. MR**1344216 (96d:14001)****22.**T. Ojika,

Modified deflation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations,*J. Math. Anal. Appl.*123 (1987), pp. 199-221. MR**881541 (88f:65085)****23.**T. Ojika, S. Watanabe, and T. Mitsui,

Deflation algorithm for the multiple roots of a system of nonlinear equations,*J. Math. Anal. Appl.*96 (1983), pp. 463-479. MR**719330 (85a:65083)****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.**A.J. Sommese, J. Verschelde and C.W. Wampler,

Numerical decomposition of the solution sets of polynomial systems into irreducible components,*SIAM J. Numer. Anal.*38(6) (2001), pp. 2022-2046. MR**1856241 (2002g:65064)****26.**A.J. Sommese, J. Verschelde, and C.W. Wampler,

Using monodromy to decompose solution sets of polynomial systems into irreducible components.

In*Application of Algebraic Geometry to Coding Theory, Physics and Computation*, edited by C. Ciliberto, F. Hirzebruch, R. Miranda, and M. Teicher. Proceedings of a NATO Conference, February 25 - March 1, 2001, Eilat, Israel, pages 297-315, Kluwer Academic Publishers. MR**1866906 (2002k:65087)****27.**A.J. Sommese, J. Verschelde and C.W. Wampler,

Symmetric functions applied to decomposing solution sets of polynomial systems,*SIAM J. Numer. Anal.*40(6) (2002), pp. 2026-2046. MR**1974173 (2004m:65069)****28.**A.J. Sommese, J. Verschelde, and C.W. Wampler,

Numerical irreducible decomposition using PHCpack,

in*Algebra, Geometry, and Software Systems*, M. Joswig and N. Takayama, eds., Springer-Verlag, 2003, pp. 109-130. MR**2011756 (2004i:65047)****29.**A.J. Sommese, J. Verschelde, and C.W. Wampler,

Homotopies for Intersecting Solution Components of Polynomial Systems,*SIAM J. Numer. Anal.*42(4) (2004), pp. 1552-1571. MR**2114290 (2005m:65111)****30.**A.J. Sommese, J. Verschelde, and C.W. Wampler,

An intrinsic homotopy for intersecting algebraic varieties,*J. Complexity*, 21 (2005), pp. 593-608. MR**2152724 (2006f:65057)****31.**A.J. Sommese, J. Verschelde, and C.W. Wampler,

Solving Polynomial Systems Equation by Equation,

in*IMA Volume 146: Algorithms in Algebraic Geometry*, A. Dickenstein, F.-O. Schreyer, and A.J. Sommese, eds., Springer-Verlag, 2007, pp. 133-152. MR**2397941 (2009g:65075)****32.**A.J. Sommese and C.W. Wampler,

Numerical algebraic geometry.

in*The Mathematics of Numerical Analysis*, edited by J. Renegar, M. Shub, and S. Smale, volume 32 of*Lectures in Applied Mathematics*, 1996, pp. 749-763.

Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics, Park City, Utah, July 17-August 11, 1995, Park City, Utah. MR**1421365 (98d:14079)****33.**A.J. Sommese and C.W. Wampler,*The numerical solution of systems of polynomials arising in engineering and science*,

World Scientific Press, Singapore, 2005. MR**2160078 (2007a:14065)****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.**J. Verschelde and R. Cools,

Symbolic homotopy construction,*Appl. Algebra Engrg. Comm. Comput.*, 4 (1993), pp. 169-183. MR**1226323 (94c:68102)****36.**J. Verschelde, P. Verlinden, and R. Cools,

Homotopies exploiting Newton polytopes for solving sparse polynomial systems,*SIAM J. Numer. Anal.*, 31(3) (1994), pp. 915-930. MR**1275120 (94m:65084)****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, K. Warwick, ed., Clarendon Press, Oxford, 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.**B. Yu and B. Dong,

A hybrid polynomial system solving method for mixed trigonometric polynomial systems,*SIAM J. Numer. Anal.*, 46(3) (2008), pp. 1503-1518. MR**2391004 (2009b:65133)****41.**Z. Zeng,

The closedness subspace method for computing the multiplicity structure of a polynomial system, in*Interactions of Classical and Numerical Algebraic Geometry*, D. Bates, G. Besana, S. Di Rocco, and C. Wampler (eds.),*Contemporary Mathematics*496 (2009), pp. 347-362. MR**2555964**

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.