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 algori...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(uH-l))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 w辻h some tricks have been implemented as a software package logcf using C language.Experiments on many benchmarks show that logcf is competitive with Root Intervals 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.展开更多
基金supported by the National Science Foundation of China under Grant Nos.61802318,61732001and 61532019
文摘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(uH-l))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 w辻h some tricks have been implemented as a software package logcf using C language.Experiments on many benchmarks show that logcf is competitive with Root Intervals 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.
