A Comparative Study of Two Real Root Isolation Methods - Akritas, A. G.; Strzebonski, A. W. (Nonlinear Analysis: Modelling and Control, 2005)
Recent progress in polynomial elimination has rendered the computation of the real roots of ill-conditioned polynomials of high degree (over 1000) with huge coefficients (several thousand digits) a critical operation in computer algebra.To rise to the occasion, the only method-candidate that has been considered by various authors for modification and improvement has been the Collins-Akritas bisection method [1], which is a based on a variation of Vincent’s theorem [2].The most recent example is the paper by Rouillier and Zimmermann [3], where the authors present “... a new algorithm, which is optimal in terms of memory usage and as fast as both Collins and Akritas’ algorithm and Krandick variant ...” [3]In this paper we compare our own continued fractions method CF [4] (which is directly based on Vincent’s theorem) with the best bisection method REL described in [3]. Experimentation with the data presented in [3] showed that, with respect to time, our continued fractions method CF is by far superior to REL, whereas the two are about equal with respect to space.
Keywords: root isolation; Vincent’s theorem; continued fractions method; bisection (or Collins-Akritas) method