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.展开更多
In this paper, we propose an algorithm for isolating real roots of a given univariate spline function, which is based on the use of Descartes＇ rule of signs and de Casteljau algorithm. Numerical examples illustrate t...In this paper, we propose an algorithm for isolating real roots of a given univariate spline function, which is based on the use of Descartes＇ rule of signs and de Casteljau algorithm. Numerical examples illustrate the flexibility and effectiveness of the algorithm.展开更多
For finding the real roots of a polynomial,we propose a clipping algorithmcalled SLEFEclipping and an isolation algorithmcalled SLEFEisolation algorithm.Ateach iterative step,the SLEFEclipping algorithm generates two ...For finding the real roots of a polynomial,we propose a clipping algorithmcalled SLEFEclipping and an isolation algorithmcalled SLEFEisolation algorithm.Ateach iterative step,the SLEFEclipping algorithm generates two broken lines boundingthe given polynomial.Then,a sequence of intervals can be obtained by computing theintersection of the sequence of broken lines with the abscissa axis.The sequence ofthese intervals converges to the root with a convergence rate of 2.Numerical examplesshow that SLEFE clipping requires fewer iterations and less computation time thancurrent algorithms,and the SLEFE isolation algorithm can compute all intervals thatcontain the roots rapidly and accurately.展开更多
基金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.
基金supported by the National Natural Science Foundation of China (Project Nos.60373093 and 60533060)
文摘In this paper, we propose an algorithm for isolating real roots of a given univariate spline function, which is based on the use of Descartes＇ rule of signs and de Casteljau algorithm. Numerical examples illustrate the flexibility and effectiveness of the algorithm.
基金the joint grant by National Natural Science Foundation ofChina(No.11471093)Thanks to the authors of references for the valuable ideas to this paper and thanksto the reviewers for their precious opinions proposed to this paper.
文摘For finding the real roots of a polynomial,we propose a clipping algorithmcalled SLEFEclipping and an isolation algorithmcalled SLEFEisolation algorithm.Ateach iterative step,the SLEFEclipping algorithm generates two broken lines boundingthe given polynomial.Then,a sequence of intervals can be obtained by computing theintersection of the sequence of broken lines with the abscissa axis.The sequence ofthese intervals converges to the root with a convergence rate of 2.Numerical examplesshow that SLEFE clipping requires fewer iterations and less computation time thancurrent algorithms,and the SLEFE isolation algorithm can compute all intervals thatcontain the roots rapidly and accurately.
