DK3: Geometric Solvers for Polynomial Systems

Robust algorithms for solving systems of polynomial equations, which are based on Bézier clipping and its variants, find all roots in a bounded domain and have second order convergence for single roots.  E.g., such techniques are needed for solving intersection problems in Computer Aided Design, but they can also be useful for applications in robotics and numerical simulation.

Recently we formulated a new geometric algorithm for solving univariate polynomials via approximation by quadratic enclosures with good convergence rates: 3 for single and 3/2 for double roots. In particular, it performs very well in the case of two roots which are relatively close to each other. We plan to explore several extensions and related applications.

Supervisor: Prof. Bert Jüttler