Fast Algorithm for Composition of the Bernstein Polynomials

Composition of Bernstein polynomials is an important research topic in computer-aided geometric design. Some numerically stable algorithms for composition, such as Blossoming algorithm and optimal algorithm, which are computationally expensive. A fast algorithm to evaluate the coefficients of the resultant polynomials based on polynomial interpolation is presented. The reconstruction matrix used in interpolation is constant if the sampling points are chosen evenly in the parametric domain. Thus it can be computed in advance. To avoid numerical error, we employ a symbolic computation algorithm to evaluate the inverse matrix. The runtime analysis shows that the proposed algorithm is the fastest one among current algorithms and it does not involve numerical instability, additional storage and code complexity problems during implementation.