Homotopy Methods For Solving Polynomial Systems With Multi-homogeneous Structure

Many problems of science and engineering can be changed into solving polynomial systems. Given a polynomial system, we always want to determine the number of isolated solutions and then compute all of them. In 1977, Garcia and Zangwill [2] and Drexler [4] independently presented theorems suggesting that homotopy continuation could be used to find the full set of isolated solutions of polynomial systems numerically. During the last two decades, this method has been developed into a reliable and efficient numerical algorithm.Consider a polynomial system:where x = {x₁, ... ,x_n) ∈ Cⁿ, P(x) = (p₁(x), ... ,p_n(x)) = 0, p_i(x) is a polynomial equation.In general, the homotopy continuation method for solving polynomial systems, which is based on Bezout theory, has to follow more curves than the number of solutions that the system (1.1) really has. Hence it may waste too much time by following those unnecessary curves. Morgan and Sommese [1] proposed the multi-homogeneous Bezout theorem. It is shown that the multi-homogeneous Bezout theorem also give an upper bound for the number of isolated solutions of a polynomial system. Different way of partitioning the variables produces different multi-homogeneous Bezout number. It is desired to find a partition whose multi-homogeneous Bezout number is the smallest among all possible variablepartitions. In fact the minimal multi-homogeneous Bezout number is usually smaller than the Bezout number. Thus the less number of paths are followed. We need to find the optimal partition which gives the minimal multi-homogeneous Bezout number, and to construct the start system with same multi-homogeneous partition.In 1990s, Wampler [3] presents an recursive algorithm to compute the multi-homogeneous Bezout number for any given partition. And then an exhaustive search method on finding the minimal multi-homogeneous Bezout number was given. This method is by computing all possible partitions to find the minimal one. However , it only works for small problems, since the computational complexity of the algorithm grows exponentially as a function of n, the number of variables. In 2000, Tiejun Li and Fengshan Bai propose the Local Search Method [7]. This method is by computing the "neighboring" partitions of a given or random partition to finding the minimal multi-homogeneous Bezout number. The computational complexity of Local Search Method is smaller than that of Wampler's exhaustive search method. But this method may fall into local minimum. In 2003, Ting Li, Zhengjiang Lin and Fengshan Bai presented two heuristic methods (Fission Method and Assembly Method) [8]. The idea of these methods is aroused by evolution mechanism. Every partition is regarded as an individual. The partitions in this generation come from the selected partition in the former generation which undergoes fission or assembly transformations. The selection scheme is to find a partition which has the minimal multi-homogeneous Bezout number in a generation. Finally, the minimal one of the partitions in all generations is selected. The computational cost of these two methods are lower than that of Wampler's exhaustive search method. Large amount of numerical computation shows that the minimal multi-homogeneous Bezout number can be obtained for most of the problems by these two methods.At the same time, Yu Bo and Cao Xiaofei [10] presented two methods (Subtree Method and Truncated Subtree Method). Subtree Method selects all the...