A fast parallel algorithm for determining all roots of a polynomial with real roots. (English) Zbl 0663.68047
The complexity class NC consists of algorithms that can be executed on a polynomial number of processors in poly-log time, measured in the size of the input. This paper shows that the computation of all roots of a polynomial in \({\mathbb{Z}}[x]\), which has only real roots is in NC.
The algorithm uses the Sturm sequence of the polynomial f to find a \(w\in {\mathbb{R}}\), which is far from zeroes of f, such that in between 1/3 and 3/4 of the number of roots of f is larger than w. A numerical contour integration will give two polynomials of smaller degree which are approximations of factors of f. By iteration of this procedure approximations of the zeroes of f can be found.
The algorithm uses the Sturm sequence of the polynomial f to find a \(w\in {\mathbb{R}}\), which is far from zeroes of f, such that in between 1/3 and 3/4 of the number of roots of f is larger than w. A numerical contour integration will give two polynomials of smaller degree which are approximations of factors of f. By iteration of this procedure approximations of the zeroes of f can be found.
Reviewer: F.van der Linden
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 65D99 | Numerical approximation and computational geometry (primarily algorithms) |
| 12D10 | Polynomials in real and complex fields: location of zeros (algebraic theorems) |
