Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleSubdivision methods for solving polynomial equations
Author(s) Bernard Mourrain, J.P. Pavone
TypeArticle in Journal
AbstractThis 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.
KeywordsResolution, Real solution, Symbolic-numeric computation, Polynomial equation, Subdivision, Bernstein basis, Descartes rule, Complexity
URL http://www.sciencedirect.com/science/article/pii/S0747717108001168
JournalJournal of Symbolic Computation
Pages292 - 306
NotePolynomial System Solving in honor of Daniel Lazard
Translation No
Refereed No