Minimizing multi-homogeneous Bézout numbers by a local search method

Authors:
Tiejun Li and Fengshan Bai

Journal:
Math. Comp. **70** (2001), 767-787

MSC (2000):
Primary 65H10

Published electronically:
October 18, 2000

MathSciNet review:
1813146

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Consider the multi-homogeneous homotopy continuation method for solving a system of polynomial equations. For any partition of variables, the multi-homogeneous Bézout number bounds the number of isolated solution curves one has to follow in the method. This paper presents a local search method for finding a partition of variables with minimal multi-homogeneous Bézout number. As with any other local search method, it may give a local minimum rather than the minimum over all possible homogenizations. Numerical examples show the efficiency of this local search method.

**1.**Shui Nee Chow, John Mallet-Paret, and James A. Yorke,*A homotopy method for locating all zeros of a system of polynomials*, Functional differential equations and approximation of fixed points (Proc. Summer School and Conf., Univ. Bonn, Bonn, 1978) Lecture Notes in Math., vol. 730, Springer, Berlin, 1979, pp. 77–88. MR**547982****2.**T. A. Gao, T. Y. Li, X. S. Wang (1999), Finding isolated zeros of polynomial systems in with stable mixed volumes, J. Symbolic Comput.**28**, 187-211. CMP**2000:01****3.**C. B. García and W. I. Zangwill,*Finding all solutions to polynomial systems and other systems of equations*, Math. Programming**16**(1979), no. 2, 159–176. MR**527572**, 10.1007/BF01582106**4.**B. Huber, B. Sturmfels (1995), A polyhedral method for solving sparse polynomial systems, Math. Comp.,**64**, 1541-1555.**5.**B. Huber and B. Sturmfels,*Bernstein’s theorem in affine space*, Discrete Comput. Geom.**17**(1997), no. 2, 137–141. MR**1424821**, 10.1007/BF02770870**6.**Tien-Yien Li,*On Chow, Mallet-Paret and Yorke homotopy for solving system of polynomials*, Bull. Inst. Math. Acad. Sinica**11**(1983), no. 3, 433–437. MR**726989****7.**T. Y. Li (1997), Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numerica, 399-436. CMP**98:06****8.**C. B. García and T. Y. Li,*On the number of solutions to polynomial systems of equations*, SIAM J. Numer. Anal.**17**(1980), no. 4, 540–546. MR**584729**, 10.1137/0717046**9.**T.-Y. Li, Tim Sauer, and James A. Yorke,*The random product homotopy and deficient polynomial systems*, Numer. Math.**51**(1987), no. 5, 481–500. MR**910860**, 10.1007/BF01400351**10.**Tien-Yien Li, Tim Sauer, and James A. Yorke,*Numerical solution of a class of deficient polynomial systems*, SIAM J. Numer. Anal.**24**(1987), no. 2, 435–451. MR**881375**, 10.1137/0724032**11.**T. Y. Li, T. Sauer, J. A. Yorke (1989), A simple homotopy for solving deficient polynomial systems, Japan J. Math. Appl. Math.**6**, 409-419.**12.**T. Y. Li, Tim Sauer, and J. A. Yorke,*The cheater’s homotopy: an efficient procedure for solving systems of polynomial equations*, SIAM J. Numer. Anal.**26**(1989), no. 5, 1241–1251. MR**1014884**, 10.1137/0726069**13.**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**, 10.1016/0096-3003(87)90063-4**14.**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**, 10.1137/0731049**15.**J. Verschelde, K. Gatermann, and R. Cools,*Mixed-volume computation by dynamic lifting applied to polynomial system solving*, Discrete Comput. Geom.**16**(1996), no. 1, 69–112. MR**1397788**, 10.1007/BF02711134**16.**Charles W. Wampler,*Bezout number calculations for multi-homogeneous polynomial systems*, Appl. Math. Comput.**51**(1992), no. 2-3, 143–157. MR**1180597**, 10.1016/0096-3003(92)90070-H**17.**Charles W. Wampler,*An efficient start system for multihomogeneous polynomial continuation*, Numer. Math.**66**(1994), no. 4, 517–523. MR**1254401**, 10.1007/BF01385710

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65H10

Retrieve articles in all journals with MSC (2000): 65H10

Additional Information

**Tiejun Li**

Affiliation:
School of Mathematical Sciences, Peking University, Beijing, P. R. China

**Fengshan Bai**

Affiliation:
Department of Mathematics, Tsinghua University, Beijing, 100084, P. R. China

Email:
fbai@math.tsinghua.edu.cn

DOI:
http://dx.doi.org/10.1090/S0025-5718-00-01303-X

Keywords:
Multi-homogeneous B\'{e}zout number,
polynomial system,
homotopy method,
local search method

Received by editor(s):
September 18, 1998

Published electronically:
October 18, 2000

Additional Notes:
Supported by National Science Foundation of China G19871047 and National Key Basic Research Special Fund G1998020306.

Article copyright:
© Copyright 2000
American Mathematical Society