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

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

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.

**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 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 -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**

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:
https://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