Logcf: an efficient tool for real root isolation

DOI10.1007/S11424-019-7361-7zbMATH Open1494.68310arXiv1209.3555OpenAlexW2995945776WikidataQ126589028 ScholiaQ126589028MaRDI QIDQ2287381FDOQ2287381

Authors: Liyun Dai, Zhe Fan, Bican Xia, Han-Wen Zhang 

Publication date: 20 January 2020

Published in: Journal of Systems Science and Complexity (Search for Journal in Brave)

Abstract: This paper revisits an algorithm for isolating real roots of univariate polynomials based on continued fractions. It follows the work of Vincent, Uspen- sky, Collins and Akritas, Johnson and Krandick. We use some tricks, especially a new algorithm for computing an upper bound of positive roots. In this way, the algorithm of isolating real roots is improved. The complexity of our method for computing an upper bound of positive roots is O(n log(u+1)) where u is the optimal upper bound satisfying Theorem 3 and n is the degree of the polynomial. Our method has been implemented as a software package logcf using C++ language. For many benchmarks logcf is two or three times faster than the function RootIntervals of Mathematica. And it is much faster than another continued fractions based software CF, which seems to be one of the fastest available open software for exact real root isolation. For those benchmarks which have only real roots, logcf is much faster than Sleeve and eigensolve which are based on numerical computation.

Full work available at URL: https://arxiv.org/abs/1209.3555

Recommendations

• SLV: a software for real root isolation
• Real root isolation for exp-log functions
• Kernel rootkits implement and detection
• Random CFI (RCFI): Efficient Fine-Grained Control-Flow Integrity Through Random Verification
• Attacks on secure logging schemes
• Even more practical secure logging: tree-based seekable sequential key generators

zbMATH Keywords

computer algebracontinued fractionsunivariate polynomialreal root isolationVincent's theorem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomials in real and complex fields: factorization (12D05)

Cites Work

• Title not available (Why is that?)
• Efficient isolation of polynomial's real roots.
• SLV: a software for real root isolation
• Title not available (Why is that?)
• Real solution isolation using interval arithmetic
• Bounds for absolute positiveness of multivariate polynomials
• Complexity of real root isolation using continued fractions
• On the complexity of real root isolation using continued fractions
• Computer Algebra in Scientific Computing
• A deterministic algorithm for isolating real roots of a real polynomial
• Architecture-aware classical Taylor shift by 1
• A new method for real root isolation of univariate polynomials
• Computing Real Roots of Real Polynomials ... and now For Real!
• Improving the performance of the continued fractions method using new bounds of positive roots

Cited In (5)

• Implementations of a new theorem for computing bounds for positive roots of polynomials
• Improving the performance of the continued fractions method using new bounds of positive roots
• logcf
• Real root isolation for exp-log-arctan functions
• Improved bounds for the CF algorithm

Uses Software

• Maple
• Mathematica
• INTLAB
• ISOLATE
• ANewDsc
• SLV

This page was built for publication: Logcf: an efficient tool for real root isolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2287381)