Subdivision methods for solving polynomial equations
This paper presents a new algorithm for solving a system of polynomials, in a domain of R(n). It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis [Sherbrooke, E.C., Patrikalakis, N.M., 1993. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design 10 (5), 379-405]. It uses a powerful reduction strategy based on univariate root finder using Bernstein basis representation and Descarte's rule. We analyse the behavior of the method, from a theoretical point of view, shows that for simple roots, it has a local quadratic convergence speed and gives new bounds for the complexity of approximating real roots in a box of R(n). The improvement of our approach, compared with classical subdivision methods, is illustrated on geometric modeling applications such as computing intersection points of implicit curves, self-intersection points of rational curves, and on the classical parallel robot benchmark problem. (C) 2008 Elsevier Ltd. All rights reserved.
subdivision polynomial equation bernstein basis complexity resolution real solution symbolic-numeric computation descartes rule