sign in
english version rss feed

inria-00070350, version 1

Subdivision methods for solving polynomial equations

Bernard Mourrain () 1, Jean-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.

  • 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
  • oai:hal.inria.fr:inria-00070350
  • From: 
  • Submitted on: Friday, 19 May 2006 20:13:47
  • Updated on: Tuesday, 23 June 2009 11:26:54
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...