Mathematics of Computation

Author(s): Tiejun Li; Fengshan Bai.
Journal: Math. Comp. 70 (2001), 767-787.
MSC (2000): Primary 65H10
Posted: October 18, 2000
Retrieve article in: PDF
This article is available free of charge

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 $\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 -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

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: 10.1090/S0025-5718-00-01303-X
PII: S 0025-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
Posted: October 18, 2000
Additional Notes: Supported by National Science Foundation of China G19871047 and National Key Basic Research Special Fund G1998020306.
Copyright of article: Copyright 2000, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS