inria-00070350, version 1
Subdivision methods for solving polynomial equations
Bernard Mourrain
1Jean-Pascal Pavone 1
Journal of Symbolic Computation 44, 3 (2009) 292-306
Abstract: This paper presents a new algorithm for solving a system of polynomials, in a domain of $ ^n$. It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis . 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 $ ^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.
- 1: GALAAD (INRIA Sophia Antipolis)
- INRIA – CNRS : UMR6621 – Université Nice Sophia Antipolis [UNS]
- Domain : Computer Science/Other
- Keywords : RESOLUTION – SYMBOLIC-NUMERIC COMPUTATION – POLYNOMIAL EQUATION – SUBDIVISION – REAL SOLUTION – BERNSTEIN – BASIS – DESCARTES RULE – COMPLEXITY
- Internal note : RR-5658
- inria-00070350, version 1
- http://hal.inria.fr/inria-00070350
- oai:hal.inria.fr:inria-00070350
- From: Rapport De Recherche Inria
- Submitted on: Friday, 19 May 2006 20:13:47
- Updated on: Tuesday, 23 June 2009 11:26:54






Associated documents

Export