Polynomial Real Roots Computation

Now most problems being computed by computers can be deduced to the problem of polynomial real roots computation, thus the process of polynomial real roots computation directly touches the efficiency and correctness of various algorithms. Therefore, seeking a faster and more exact algorithm for polynomial real roots computation, has became so necessary. At present, most methods focus on polynomial real roots computation can be divided into two varieties, numerical computing and symbolic computing, the latter has attracted more and more attention for its accuracy. And in actual engineering, as inevitable error caused by measuring precision and the limited precision of most computers, it always can not achieve exact coefficient but interval coefficient polynomials, this is a problem cannot be ignored.This paper revisits a real roots isolation frame built by Rouillier and Zimmer-mann, and advances a traverse strategy upon the frame on the binary tree which composed by binary interval during real roots isolating process. This can exert the power of Descartes' rule of sign more effective, and it can reduce the transformation by the corresponding polynomial of every nodes on the binary tree. The experimental result indicates the computing time can be reduced to 60% of Rouillier method by real coefficient polynomials with this improvement, and by real root polynomials the computing time can be reduced to 80% of Rouillier method with this improvement.This paper also analyzes the interval roots computation of interval coefficient polynomial, and advances a method to compute the interval roots of interval polynomials by computing the real roots of boundary polynomials. This method lower the complexity of original problem by transforming the computation of interval roots into the computation of real roots. Moreover, by reviewing the geometric property of upper/lower boundary polynomials, that is the upper boundary polynomial is always above the lower boundary polynomial, this paper shows an algorithm to speed up the real roots isolation of boundary polynomials, it firstly accomplishes the real roots iso- lation of one boundary polynomial, and quicken the speed of real roots isolation of the other boundary polynomial with front computing result. The experimental result indicates, if the real roots of lower boundary polynomial have been isolated firstly, the computing time can be reduced to 70%-80% with this speedup algorithm while computing the real roots of upper boundary polynomial. As the time of real roots isolation of both boundary polynomial can be seemed same, the total computing time of real roots isolation of boundary polynomial can be reduced to 85%-90% with this improvement.