Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

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.

References [Enhancements On Off] (What's this?)

  • 1. S. N. Chow, J. Mallet-Paret, J. A. Yorke (1979), A homotopy method for locating all zeros of a system of polynomials, In ``Functional differential equations and approximation of fixed points"(H. O. Peitgen, H. O. Walther, eds.) Lecture Notes in Mathematics Vol. 730, Springer-Verlag (Berlin, Heidelberg), 77-88.MR 80k:58012
  • 2. 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. CMP 2000:01
  • 3. C. B. Garcia, W. I. Zangwill (1979), Finding all solutions to polynomial systems and other systems of equations, Math. Programming, 16, 159-176.MR 80f:65057
  • 4. B. Huber, B. Sturmfels (1995), A polyhedral method for solving sparse polynomial systems, Math. Comp., 64, 1541-1555.
  • 5. B. Huber, B. Sturmfels (1997), Bernstein's theorem in affine space, Discrete Comput. Geom., 17, 137-141. MR 98b:52014
  • 6. T. Y. Li (1983), On Chow, Mallet-Paret and Yorke homotopy for solving system of polynomials, Bull. Inst. Math. Acad. Sinica, 11 No. 3, 433-437. MR 85k:58015
  • 7. T. Y. Li (1997), Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numerica, 399-436. CMP 98:06
  • 8. T. Y. Li, C. B. Garcia (1980), On the number of solutions to polynomial systems of equations, SIAM J. Numer. Anal. 17, 540-546. MR 81m:65074
  • 9. T. Y. Li, T. Sauer, J. A. Yorke (1987), The random product homotopy and deficient polynomial systems, Numer. Math. 51, 481-500. MR 88j:65108
  • 10. T. Y. Li, T. Sauer, J. A. Yorke (1987), Numerical solution of a class of deficient polynomial systems, SIAM J. Numer. Anal. 24, 435-451. MR 89e:90181
  • 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, T. Sauer, J. A. Yorke (1989), The cheater's homotopy: an efficient procedure for solving systems of polynomial equations, SIAM J. Numer. Anal. 26, 1241-1251.MR 90m:65105
  • 13. A. P. Morgan, A. J. Sommese (1987), A homotopy for solving general polynomial systems that respect $m$-homogeneous structures, Appl. Math. Comput., 24, 101-113. MR 88j:65110
  • 14. J. Verschelde, P. Verlinden, R. Cools (1994) Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal., 31, 915-930.MR 94m:65084
  • 15. J. Verschelde, K. Gatermann, R. Cools (1996) Mixed-volume computation by dynamic lifting applied to polynomial systems solving, Discrete Comput. Geom. 16, 69-112. MR 98g:68171
  • 16. C. W. Wampler (1992), Bézout number calculations for multi-homogeneous polynomial systems, Appl. Math. Comput., 51, 143-157.MR 93f:65047
  • 17. C. W. Wampler (1994), An efficient start system for multihomogeneous polynomial continuation, Numer. Math., 66, 517-523. MR 94i:65065

Similar Articles

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

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

American Mathematical Society