Symmetric Newton polytopes for solving sparse polynomial systems (Q1894795)

The authors approach the computation of isolated solutions of a given polynomial system by homotopy methods, especially by methods for constructing symmetric homotopies. In this paper it will be shown how the lifting algorithm proposed by \textit{B. Huber} and \textit{B. Sturmfels} [A polyhedral method for solving sparse polynomial systems, Math. Comput. 64, No. 212, 1541-1555 (1995)]can be applied to symmetric Newton polytopes. The paper is structured as follows. The second section recalls the terminology and notations from the theory of polytopes. Then in the third section the lifting algorithm for solving systems of Laurent polynomials is presented. This algorithm uses a certain homotopy and includes the determination of the BKK bound of a Laurent polynomial system [cf. \textit{D. N. Bernshtejn, A. G. Kushnirenko} and \textit{A. G. Khovanskij}, Uspeki Mat. Nauk 31, No. 3(189), 201-202 (1976; Zbl 0354.14001)]. In the fourth section, symmetric Newton polytopes and subdivisions are discussed. The symmetric lifting function, which leads to the construction of a symmetric mixed subdivision and to a symmetric homotopy, is described in the fifth section. Many applications with practical significance of the method are given in this paper.