Real zeroes of polynomials. (English) Zbl 0533.68038

Computer algebra, symbolic and algebraic computation, Comput. Suppl. 4, 83-94 (1982).
[For the entire collection see Zbl 0491.00019.]
Let \({\mathcal A}\) be a polynomial over \({\mathcal Z}\), \({\mathcal Q}\) or \({\mathcal Q}(\alpha)\) where \(\alpha\) is a real algebraic number. The problem is to compute a sequence of disjoint intervals with rational endpoints, each containing exactly one real zero of \({\mathcal A}\) and together containing all real zeroes of \({\mathcal A}\). In the paper four algorithms are described and the maximum computation times are given: 1) an algorithm due to Kronecker based on the minimum root separation, 2) Sturm’s algorithm, 3) an algorithm based on Rolle’s theorem due to Collins and Loos and 4) the modified Uspensky algorithm due to Collins and Aritas. For the last algorithm a recursive version with correctness proof is given which appears in print for the first time.
Reviewer: G.Matthiessen


68W30 Symbolic computation and algebraic computation
65G30 Interval and finite arithmetic
26C15 Real rational functions


Zbl 0491.00019