Abstract
Computing upper bounds of the positive real roots of some polynomials is a key step of those real root isolation algorithms based on continued fraction expansion and Vincent's theorem. The authors give a new algorithm for computing an upper bound of positive roots in this paper. The complexity of the algorithm is O(n log(u+1)) additions and multiplications where u is the optimal upper bound satisfying Theorem 3.1 of this paper and n is the degree of the polynomial. The method together with some tricks have been implemented as a software package logcf using C language. Experiments on many benchmarks show that logcf is competitive with RootIntervals of Mathematica and the function realroot of Maple averagely and it is much faster than existing open source real root solvers in many test cases.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Collins G and Akritas A, Polynomial real roots isolation using descartes' rule of signs, Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation, New York, 1976.
Kobel A, Rouillier F, and Sagraloff M, Computing real roots of real polynomials… and now for real, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, Waterloo, 2016, 303–310.
Rouillier F and Zimmermann P, Efficient isolation of polynomials' real roots, Comput. Math. Appl., 2004, 162(4): 33–50.
Tsigaridas E, Slv: A software for real root isolation, ACM Commun. Comput. Algebra, 2016 50(3): 117–120.
Eigenwillig A, Real root isolation for exact and approximate polynomials using Descartes' rule of signs, PhD thesis, Saarland University, 2008.
Eigenwillig A, Kettner L, Krandick W, et al., A descartes algorithm for polynomials with bit-stream coefficients, CASC, Springer, 2005, 138–149.
Mehlhorn K and Sagraloff M, A deterministic algorithm for isolating real roots of a real polynomial, J. Symb. Comput. 2011, 46: 70–90.
Akritas A, Strzebonski A, and Vigklas P, Improving the performance of the continued fractions new bounds of positive roots, Nonlinear Analysis: Modelling and Control, 2008, 13(3): 365–279.
Sharma V, Complexity of real root isolation using continued fractions, Theor. Comput. Sci., 2008, 409(2): 292–310.
Tsigaridas E P and Emiris I Z, On the complexity of real root isolation using continued fractions, Theor. Comput. Sci., 2008, 392: 158–173.
Hemmer M, Tsigaridas E, Zafeirakopoulos Z, et al., Experimental evaluation and cross-benchmarking of univariate real solvers, P roceedin gs of the 2009 Conference on Symbolic Numeric Computation, ACM, Kyoto, 2009, 45–54.
Xia B and Zhang T, Real solution isolation using interval arithmetic, Comput. Math. Appl., 2006, 52: 853–860.
Zhang T and Xia B, A new method for real root isolation of univariate polynomials, Mathematics in Computer Science, 2007, 1(2): 305–320.
Hammer R, C++ Toolbox for Verified Scientific Computing - Theory, Algorithms and Programs: Basic Numerical Problems, Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1995.
Rump S, INTLAB - Interval Laboratory. Developments in Reliable Computing, Ed. by Csendes T, Kluwer Academic Publishers, Dordrecht, 1999, 77–104. http://www.ti3.tu-harburg.de/rump/.
Ştefănescu D, New bounds for the positive roots of polynomials, J. Universal Comput. Sci. 2005, 11(12): 2132–2141.
Hong H, Bounds for absolute positiveness of multivariate polynomials, J. Symb. Comput., 1998, 25(5): 571–585.
Gerhard J, Modular algorithms in symbolic summation and symbolic integration, Lecture Notes in Computer Science, Springer Press, 2004.
Johnson J R, Krandick W, and Ruslanov A D, Architecture-aware classical taylor shift by 1, ISSAC, ACM, Beijing, 2005, 200–207.
Johnson J R, Krandick W, Richardson D, et al., High-performance implementations of the descartes method, ISSAC ACM, Genoa, 2006, 154–161.
Author information
Authors and Affiliations
Corresponding author
Additional information
The research was supported by the National Science Foundation of China under Grant Nos. 61802318, 61732001 and 61532019.
This paper was recommended for publication by Editor LI Hongbo.
Rights and permissions
About this article
Cite this article
Dai, L., Fan, Z., Xia, B. et al. Logcf: An Efficient Tool for Real Root Isolation. J Syst Sci Complex 32, 1767–1782 (2019). https://doi.org/10.1007/s11424-019-7361-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-019-7361-7