Communications in Information and Systems

Volume 17 (2017)

Number 2

Efficient rational quadratic clipping method for computing roots of a polynomial

Pages: 115 – 131

DOI: https://dx.doi.org/10.4310/CIS.2017.v17.n2.a3

Authors

Xiao-Diao Chen (Key Laboratory of Complex Systems Modeling and Simulation, Hangzhou Dianzi University, Hangzhou, China; and Department of MBE, City University of Hong Kong)

Longquan Wang (Key Laboratory of Complex Systems Modeling and Simulation, Hangzhou Dianzi University, Hangzhou, China)

Ligeng Chen (Key Laboratory of Complex Systems Modeling and Simulation, Hangzhou Dianzi University, Hangzhou, China)

Yigang Wang (Key Laboratory of Complex Systems Modeling and Simulation, Hangzhou Dianzi University, Hangzhou, China)

Weiyin Ma (Department of MBE, City University of Hong Kong)

Abstract

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.

Published 1 February 2018