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

HTML articles powered by AMS MathViewer

- by Tiejun Li and Fengshan Bai PDF
- Math. Comp.
**70**(2001), 767-787 Request permission

## Abstract:

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.## References

- 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** - T. A. Gao, T. Y. Li, X. S. Wang (1999), Finding isolated zeros of polynomial systems in $\mathbf { C}^n$ with stable mixed volumes, J. Symbolic Comput.
**28**, 187–211. - 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**, DOI 10.1007/BF01582106 - B. Huber, B. Sturmfels (1995), A polyhedral method for solving sparse polynomial systems, Math. Comp.,
**64**, 1541-1555. - B. Huber and B. Sturmfels,
*Bernstein’s theorem in affine space*, Discrete Comput. Geom.**17**(1997), no. 2, 137–141. MR**1424821**, DOI 10.1007/BF02770870 - 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** - T. Y. Li (1997), Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numerica, 399-436.
- C. B. García and Tien-Yian Li,
*On the number of solutions to polynomial systems of equations*, SIAM J. Numer. Anal.**17**(1980), no. 4, 540–546. MR**584729**, DOI 10.1137/0717046 - 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**, DOI 10.1007/BF01400351 - 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**, DOI 10.1137/0724032 - 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. - 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**, DOI 10.1137/0726069 - 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 - 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 - 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**, DOI 10.1007/BF02711134 - Charles W. Wampler,
*Bezout number calculations for multi-homogeneous polynomial systems*, Appl. Math. Comput.**51**(1992), no. 2-3, 143–157. MR**1180597**, DOI 10.1016/0096-3003(92)90070-H - Charles W. Wampler,
*An efficient start system for multihomogeneous polynomial continuation*, Numer. Math.**66**(1994), no. 4, 517–523. MR**1254401**, DOI 10.1007/BF01385710

## 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
- 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.
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp.
**70**(2001), 767-787 - MSC (2000): Primary 65H10
- DOI: https://doi.org/10.1090/S0025-5718-00-01303-X
- MathSciNet review: 1813146