Next: , Up: Numerical algorithms

5.2.1 Polynomials in power form

GEOMLIB contains a general polynomial solver which is used in most of curves computations (see Rational Bezier curves).

The power form of the general polynomial P(t) is



Each nonzero polynomial of degree n has at most n real roots (mathgeomlib4). The following function finds all these roots in the increasing order:

     int geom_polynomial_solve(uns degree, double *coef,
                               uns flags, double *result);

To achieve a good numerical stability, all computations work in the double precision. Possible options to the algorithm can be passed in flags parameter as an OR combination of the following bits:

Returns only the minimal root if exists.
Returns only the roots in the closed interval [0, 1].
Returns each root with multiplicity k as k identical entries in the resulting array.

We have implemented closed form solvers up to degree 4 (including), because they are faster then the general iterative solver designed for higher degrees. Mathematical basis of these algorithms can be found at (Cubic Equation, Quartic Equation).

Roots of the degree 5 or higher polynomials can be found with Jenkins-Traub iterative algorithm. We have translated the C++ implementation from to C99 standard. Detailed description of the algorithm is beyound the scope of this documentation, but some brief comments can be found in the source file geomlib/polynomial.c.