Computing the optimal partition of variables in multi-homogeneous homotopy methods (Q1774889)

The authors consider the multi-homogeneous homotopy continuation method for finding all isolated solutions of systems of polynomial equations. The number of solution curves to be followed in this homotopy method, the so-called multi-homogeneous Bézout number, depends on the partition of the variables. A smaller number of solution curves to be followed reduces the computational cost of the method. Therefore, the problem of finding the partition of the variables which minimizes the multi-homogeneous Bézout number is studied. A new method, the randomized fission method, for solving this combinatorial optimization problem is presented. A crucial part of this method is the so-called random bipartition search (RBS). For RBS global convergence with probability one is shown and the expected number of search steps is estimated. Numerical experiments are presented which show the efficiency of the new method in comparison with other methods from the literature.