Heuristic Methods For Computing The Minimal Multi-homogenous Bézout Number

Finding all isolated solutions of polynomial systems of equations has very wide applications in many fields of science and engineering. During the last two decades, homotopy continuation method has been developed to be a reliable and efficient numerical algorithm to solve such problem. Since the technique of curve following is sophisticated,it becomes more critical to reduce the number of solution curves being followed. The m-homogeneous homotopy method gives a better upper bound for the number of solutions to a polynomial system. However, two crucial problems are conferred when getting this bound. One is finding a variable partition with the minimal Bézout number among all possible variable partitions, and the second one is the computation of m-homogeneous Bézout number for any given variable partition. The complexity of them is exponential. Therefore, in this article, heuristic methods are given for both problems to get a more satisfactory approximating solution within a reasonable time.For the first problem, the successive best selection method is presented based the idea of the greedy method. It is the synthesis of Fission and Assemble Methods. Some numerical comparison about them is also given. For the second problem, we transform it to the computation of permanent, and Monte Carlo method and Markov Chain Monte Carlo method are used to sample. To sidestep the deficiency of sampling way, we take a precondition on the initial polynomial system, and use the optimal solution of new system to approximate the optimal solution of initial system. Since this method is heuristic, we give a large of numerical experimental to show its efficiency.