Subdivision methods for solving polynomial equations |
| |
Authors: | B Mourrain JP Pavone |
| |
Affiliation: | GALAAD, INRIA Méditerranée, BP 93, 06902 Sophia Antipolis, France |
| |
Abstract: | This paper presents a new algorithm for solving a system of polynomials, in a domain of Rn. 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 Rn. 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. |
| |
Keywords: | Resolution Real solution Symbolic-numeric computation Polynomial equation Subdivision Bernstein basis Descartes rule Complexity |
本文献已被 ScienceDirect 等数据库收录! |
|