Computer Science Colloquium

Subdivision Methods for Solving Polynomial Equations

Bernard Mourrain
Project GALAAD, INRIA, France

Friday, October 20, 2006, 2006 3:00 - 4:30 PM
Room 1013 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Colloquium Information:


Vikram Sharma href="">, (212) 998-3490


> In this presentation, we consider subdivision methods for solving polynomial equations, using the representation of polynomials in the Bernstein basis. We recall results on univariate polynomial solvers and describe a generalisation of the method for solving a system of polynomial equations, in a bounded domain. It uses a powerful reduction strategy based on a univariate root finder. We analyse its behavior, from a theoretical point of view, and 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 n-dimensional box. The extension for computing the topology of implicit curves and surfaces is discusssed and results on the complexity of the approach are detailed. We conclude our presentation, with some demonstrations based on the C++ library synaps and the geometric modeler axel.

top | contact