Polynomials Root-Finding Using a SLEFE-Based Clipping Method

Abstract

For finding the real roots of a polynomial, we propose a clipping algorithm called SLEFE clipping and an isolation algorithm called SLEFE isolation algorithm. At each iterative step, the SLEFE clipping algorithm generates two broken lines bounding the given polynomial. Then, a sequence of intervals can be obtained by computing the intersection of the sequence of broken lines with the abscissa axis. The sequence of these intervals converges to the root with a convergence rate of 2. Numerical examples show that SLEFE clipping requires fewer iterations and less computation time than current algorithms, and the SLEFE isolation algorithm can compute all intervals that contain the roots rapidly and accurately.

Keywords

Polynomial / Root-finding / SLEFE clipping / Real root interval isolation

References

[1] Smale S. Mathematical problems for the next century. Math. Intel.. 1998, 20 2 7-15

[2] Nishita T, Sederberg TW, Kakimoto M. Ray tracing trimmed rational surface patches. ACM SIGGRAPH Comput. Graph.. 1990, 24 4 337-345

[3] Efremov, A., Havran, V., Seidel, H. P.: Robust and numerically stable bezier clipping method for ray tracing NURBS surfaces. In: Spring Conference on Computer Graphics, pp. 127–135 (2005)

[4] Choi YK, Wang W, Liu Y . Continuous collision detection for two moving elliptic disks. Robot. IEEE Trans.. 2006, 22 2 213-224

[5] Wen-Tsun W. Basic principles of mechanical theorem proving in elementary geometries. J. Automat. Reason.. 1986, 2 3 221-252

[6] Cox DA, Little JB, O’shea D. Using Algebraic Geometry. 1998 New York: Springer

[7] Buchberger, B.: Grobner bases: an algorithmic method in polynomial ideal theory. In: Multidimensional Systems Theory, pp. 184–232 (1985)

[8] Sederberg TW, Nishita T. Curve intersection using Bézier clipping. Comput. Aided Des.. 1990, 22 9 538-549

[9] Bartoň M, Jüttler B. Computing roots of polynomials by quadratic clipping. Comput. Aided Geomet. Des.. 2007, 24 3 125-141

[10] Liu L, Zhang L, Lin B . Fast approach for computing roots of polynomials using cubic clipping. Comput. Aided Geomet. Des.. 2009, 26 5 547-559

[11] Chen XD, Ma W. Rational cubic clipping with linear complexity for computing roots of polynomials. Appl. Math. Comput.. 2016, 273 1051-1058

[12] Chen XD, Ma W, Ye Y. A rational cubic clipping method for computing real roots of a polynomial. Comput. Aided Geomet. Des.. 2015, 38 40-50

[13] Chen XD, Ma W. A planar quadratic clipping method for computing a root of a polynomial in an interval. Comput. Graph.. 2015, 46 89-98

[14] Peters J, Wu X. SLEVEs for planar spline curves. Comput. Aided Geomet. Des.. 2004, 21 6 615-635

[15] Peters J. Efficient One-Sided Linearization of Spline Geometry. 2003 Berlin: Springer

[16] Peters, J.: Mid-structures linking curved and piecewise linear geometry. In: Seattle, Geometric Modeling and Computing, pp. 453–468 (2003)

[17] Wu, X., Peters, J.: The SubLiME package (subdividable linear maximumnorm enclosure). http://www.cise.ufl.edu/research/SurfLab/download/SubLiME.tar.gz

Funding

National Natural Science Foundation of China(No. 11471093)