Logcf: an efficient tool for real root isolation

DOI10.1007/S11424-019-7361-7MaRDI QIDQ2287381zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

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

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)