The Preconditioning Method For Solving Polynomial Systems Numerically

Finding all isolated solutions of a polynomial system is an important topic inmodern pure and applied mathematics. It has wide applications in theoretical physics,large scale power systems, robotics control, etc.Homotopy continuation method is a reliable and efcient numerical algorithm forfinding all isolated zeros of polynomial systems. However, the number of curves whichneed to be tracked in the classical hometopy continuation method equals to Be′zoutnumber, which is too large for most of the deficient and large scale problems arising inpractice. This makes the homotopy continuation method low in efciency. The multi-homogeneous homotopy continuation method improves this by considering the optimalhomogeneous structure of the polynomial system. The multi-homogeneous Be′zoutnumber also gives the upper bound of the number of isolated solutions for a polyno-mial system. Diferent variable partition corresponds to diferent multi-homogeneousBe′zout number. Computing the minimal multi-homogeneous Be′zout number of a poly-nomial system is essentially attributed to two NP-hard problems:(1) Searching thevariable partition which has the minimal multi-homogeneous Be′zout number amongall possible variable partitions;(2) Computing the corresponding multi-homogeneousBe′zout number for a given variable partition.Preconditioning achieves a great success in solving linear algebraic systems ofequations. In this paper, we adopt the preconditioning ideas to the polynomial systemsand give a preconditioner based on a graph model to the multi-homogenous homotopycontinuation method. A bipartite graph model is constructed to represent the structureof a polynomial system. A variable of the polynomial system is corresponding to a ver-tex and a variable product is corresponding to an edge of a graph. Exploring the linkingstructure of the bipartite graph, block structures are detected in the variable partitions.The block structures are taken as a preconditioner, which could reduce the number ofvariable partitions dramatically. Numerical computations show the efciency of the preconditioning method.Another kernel problem for determining the optimal variable partition is to com-pute the multi-homogeneous Be′zout number for a given variable partition. This isequivalent to the computation of matrix permanent. In this paper, a novel algorithm forpermanent of sparse graph is proposed so that the computation efciency improves sig-nificantly when the order of the matrix is more than70. Moreover, we attain a new al-gorithm for computing the permanental polynomial so that the scale of the computablepermanental polynomial becomes larger. As an important application, we consider aproblem from chemical graph theory.