Bernstein多项式的快速复合算法

在计算机辅助几何设计中，Bernstein多项式的复合是一个重要的研究课题。目前，实现复合的方法主要有Blossoming算法和优化的Blossoming算法。这类方法虽然是数值稳定的，但是计算量很大，存储空间和程序复杂性方面也要求较高，文中基于多项式插值和符号运算，提出了一种新的复合算法。理论分析表明，新算法不但保持了数值稳定性，而且在计算量，存储空间和程序复杂性方面明显优于已有算法。

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.