Polynomial real root isolation using Descarte's rule of signs

George E. Collins, Alkiviadis G. Akritas

1976 · 196 citations · 4 references

DOIFull text

Open access

Concepts

Abstract

Uspensky's 1948 book on the theory of equations presents an algorithm, based on Descartes' rule of signs, for isolating the real roots of a squarefree polynomial with real coefficients. Programmed in SAC-1 and applied to several classes of polynomials with integer coefficients, Uspensky's method proves to be a strong competitor of the recently discovered algorithm of Collins and Loos. It is shown, however, that it's maximum computing time is exponential in the coefficient length. This motivates a modification of the Uspensky algorithm which is quadratic in the coefficient length and which also performs well in the practical test cases.

References

4