Computer Science Colloquium
Subdivision Methods for Solving Polynomial Equations
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: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html
Vikram Sharma href="mailto:firstname.lastname@example.org">email@example.com, (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.
| contact firstname.lastname@example.org