A two-steps algorithm for approximating real roots of a polynomial in Bernstein basis

The surface/curve intersection problem, through the resultants process results in a high degree (n≥100) polynomial equation on [0,1] in the Bernstein basis. The knowledge of multiplicities of the roots is critical for the topological coherence of the results. In this aim, we propose an original two-steps algorithm based on successive differentiations which separates any root (even multiple) and guarantees that the assumptions of Newton global convergence theorem are satisfied. The complexity is ϑ(n4) but the algorithm can easily be parallelized. Experimental results show its efficiency when facing ill-conditioned polynomials.