RESOLUTION OF MULTIPLE ROOTS OF NONLINEAR POLYNOMIAL SYSTEMS
Kwang Hee Ko, Takis Sakkalis, N. M. PATRIKALAKIS · International Journal of Shape Modeling · 2005
In this paper we discuss the roots and multiplicities of univariate and bivariate nonlinear polynomial systems and present methods to compute them robustly. For univariate polynomial systems, we propose an algorithm called the Topological Degree Bisection (TDB) algorithm which is developed based on the concept of the topological degree of a certain Gauss map which is deduced from input polynomials. The algorithm subdivides an input domain and computes the topological degree for each subdivided domain, which provides information on root existence inside the domain and the multiplicities. This process continues until the size of the subdivided regions which contain roots is less than a certain tolerance. In the bivariate polynomial system case, we use a combination of resultants and the TDB algorithm to develop a procedure for locating the roots and computing their multiplicities. Our methods are robust and global in nature. The proposed methods are compared with a subdivision method for root finding, the Interval Projected Polyhedron (IPP) algorithm and applied for the improvement of the IPP algorithm. Complexity analysis of the proposed methods is discussed with examples which illustrate our techniques.