Communications in Information and Systems
Volume 17 (2017)
Efficient rational quadratic clipping method for computing roots of a polynomial
Pages: 115 – 131
The root-finding problem is one of key issues for visualizing implicit curves and surfaces, and has wide applications in computer-aided design, computer graphics and geometric computing for image and video. This paper presents a rational quadratic clipping method for computing a simple root of a polynomial $f(t)$ of degree $n$ within an interval, which preserves the optimal computation stability of the Bernstein–Bézier representation. Different from previous clipping methods based on interpolation, it optimizes the selection of the inner point, which can achieve the convergence rate $12$ by using rational quadratic polynomials. Difference from previous clipping methods by computing bounding polynomials, it provides a simple method of linear complexity to directly bound the root; at the same time, it needs to compute the roots of quadratic polynomials and avoids solving cubic equations, and leads to a higher computational efficiency. In principle, it also works well for a non-polynomial case. Numerical examples show higher convergence rate and better computation efficiency of the new method.
This research was partially supported by the National Science Foundation of China (61672009,61502130) and City University of Hong Kong (SRG 7004452).