Logcf: an efficient tool for real root isolation

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

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

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

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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient isolation of polynomial's real roots.
• SLV
• 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!

Cited In (2)

• logcf
• Real root isolation for exp-log-arctan functions

Uses Software

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

Recommendations

• Title not available (Why is that?) 👍 👎
• SLV 👍 👎
• Even More Practical Secure Logging: Tree-Based Seekable Sequential Key Generators 👍 👎
• Random CFI (RCFI): Efficient Fine-Grained Control-Flow Integrity Through Random Verification 👍 👎
• Kernel rootkits implement and detection 👍 👎
• Attacks on Secure Logging Schemes 👍 👎

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)