Improved subdivision scheme for the root computation of univariate polynomial equations

Abstract

In this paper, a subdivision method of computing the roots of a univariate polynomial equation is proposed using novel bounding methods. The equation is converted into a Bezier curve, and the root computation problem is transformed into the geometric problem of intersection computation between the curve and an axis, which can be solved using a bound of the curve and subdivision. Four different bounding schemes are compared, and new hybrid bounding schemes are proposed for use in the root computation. In particular, the convex hull and the quasi-interpolating bound are combined to produce a smaller polygonal bound, which is then used for the root computation of the input equation. The new bounding scheme provides improved robustness and performance compared to the existing convex hull-based method, e. g., the Projected Polyhedron algorithm. Examples are provided to demonstrate the performance of the proposed method, which shows that the proposed approach is superior to the existing one. (C) 2013 Elsevier Inc. All rights reserved.