Subdivision methods for solving polynomial equations

Bernard Mourrain 1 Jean-Pascal Pavone 1
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070350
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:13:47 PM
Last modification on : Wednesday, April 17, 2019 - 4:07:57 PM
Long-term archiving on : Sunday, April 4, 2010 - 9:00:58 PM

Identifiers

  • HAL Id : inria-00070350, version 1
  • DOI : 10.1016

Collections

Citation

Bernard Mourrain, Jean-Pascal Pavone. Subdivision methods for solving polynomial equations. Journal of Symbolic Computation, Elsevier, 2009, 44 (3), pp.292-306. ⟨10.1016⟩. ⟨inria-00070350⟩

Share

Metrics

Record views

480

Files downloads

1115