Algorithms for polynomials in Bernstein form

Abstract

Aspects of the formulation and numerical stability of geometric modeling algorithms in the Bernstein polynomial basis are further explored. Bernstein forms for various basic polynomial procedures (the arithmetic operations, substitution of polynomials, elimination of variables, determination of greatest common divisors, etc.) required in such algorithms are developed, and are found to be of similar complexity to their customary power forms. This establishes the viability of systematic computation with the Bernstein form, avoiding the need for (numerically unstable) basis conversions. Procedures which nominally improve root condition numbers-the power-to-Bernstein conversion and Bernstein degree elevation and subdivision techniques-are examined in greater detail. These procedures are found to have a relatively poor inherent conditioning, which essentially cancels the expected improvement, and their explicit use does not therefore provide a means of enhancing numerical stability. We also examine the condition of computation in floating point arithmetic of the power and Bernstein formulations for the basic polynomial procedures. However, the detailed dependence of the computational errors on the input parameters, the algorithm structure, and the floating point system preclude comparisons as definitive and general as those pertaining to the root condition numbers in the power and Bernstein bases. Empirical evaluation of carefully selected test cases may provide firmer conclusions in this regard. © 1988.