The computation of multiple roots of a Bernstein basis polynomial

The Bernstein basis is used extensively in geometric modelling because of its enhanced numerical properties and elegant geometric properties in the unit interval. The computation of the points of intersection of curves and surfaces is an important problem in geometric modelling, and it gives rise to a polynomial equation. Although there is an extensive literature on numerical methods for the solution of polynomial equations, they fail to address satisfactorily an important consideration of the polynomial equations that arise in geometric modelling. In particular, multiple roots are of particular interest because they define conditions of tangency, which are important for smooth intersections of curves and surfaces.
There are, however, significant numerical problems associated with the computation of multiple roots of a polynomial because of their instability - a small perturbation in the coefficients of the polynomial is sufficient to cause the roots of the polynomial to break up into complex conjugate pairs, which is unsatisfactory. This presentation will show that multiple roots of a polynomial can be computed using an algorithm developed by Gauss. Although this algorithm is conceptually simple, its computational implementation is not trivial because it involves many greatest common divisor computations and polynomial divisions (deconvolutions), both of which are ill-posed operations. Furthermore, the combinatorial factors that arise in computations with Bernstein polynomials can cause numerical problems, which must also be considered.
It will be shown that structure-preserving matrix methods, applied to the Sylvester resultant matrix, allow the development of a Bernstein basis polynomial root finder, such that if an inexact form f(y) of an exact Bernstein basis polynomial ˆ f(y) that has multiple roots is specified, then the complex conjugate pairs of roots of f(y) that originate from the same multiple root of ˆ f(y) can be 'sewn' together, thereby preserving in the roots of f(y) an important property of the roots of ˆ f(y). The talk will include an elegant geometric explanation of the method and numerical examples.

Joab Winkler obtained his undergraduate degree from Imperial College of Science and Technology, and his PhD from University College London. He then worked in industry for a few years, before returning to academia, and he is now Reader in The Department of Computer Science at The University of Sheffield. His main research interest is numerical and algebraic problems in geometric modelling, which led to an interest in the development of robust methods for computations on resultant matrices. He has applied these robust methods to approximate greatest common divisor computations using resultant matrices, and the development of a polynomial root solver that preserves multiple roots of a Bernstein basis polynomial. More recently, he has applied resultant matrices to the problem of image deblurring when the cause of the blur is not known, that is, the problem of blind image deconvolution.