Geodesic
On the Various Bisection Methods Derived from Vincent’s Theorem
Serdica Journal of Computing, Tome 2 (2008) no. 1, pp. 89-104.

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

In 2000 A. Alesina and M. Galuzzi presented Vincent’s theorem “from a modern point of view” along with two new bisection methods derived from it, B and C. Their profound understanding of Vincent’s theorem is responsible for simplicity — the characteristic property of these two methods. In this paper we compare the performance of these two new bisection methods — i.e. the time they take, as well as the number of intervals they examine in order to isolate the real roots of polynomials — against that of the well-known Vincent-Collins-Akritas method, which is the first bisection method derived from Vincent’s theorem back in 1976. Experimental results indicate that REL, the fastest implementation of the Vincent-Collins-Akritas method, is still the fastest of the three bisection methods, but the number of intervals it examines is almost the same as that of B. Therefore, further research on speeding up B while preserving its simplicity looks promising.
Keywords: Vincent’s Theorem, Real Root Isolation Method, Bisection Method, Continued Fraction Method, Descartes’ Method, Modified Uspensky’s Method 
@article{SJC_2008_2_1_a6,
     author = {Akritas, Alkiviadis and Strzebo\'nski, Adam and Vigklas, Panagiotis},
     title = {On the {Various} {Bisection} {Methods} {Derived} from {Vincent{\textquoteright}s} {Theorem}},
     journal = {Serdica Journal of Computing},
     pages = {89--104},
     publisher = {mathdoc},
     volume = {2},
     number = {1},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2008_2_1_a6/}
}
TY  - JOUR
AU  - Akritas, Alkiviadis
AU  - Strzeboński, Adam
AU  - Vigklas, Panagiotis
TI  - On the Various Bisection Methods Derived from Vincent’s Theorem
JO  - Serdica Journal of Computing
PY  - 2008
SP  - 89
EP  - 104
VL  - 2
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJC_2008_2_1_a6/
LA  - en
ID  - SJC_2008_2_1_a6
ER  - 
%0 Journal Article
%A Akritas, Alkiviadis
%A Strzeboński, Adam
%A Vigklas, Panagiotis
%T On the Various Bisection Methods Derived from Vincent’s Theorem
%J Serdica Journal of Computing
%D 2008
%P 89-104
%V 2
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJC_2008_2_1_a6/
%G en
%F SJC_2008_2_1_a6
Akritas, Alkiviadis; Strzeboński, Adam; Vigklas, Panagiotis. On the Various Bisection Methods Derived from Vincent’s Theorem. Serdica Journal of Computing, Tome 2 (2008) no. 1, pp. 89-104. http://geodesic.mathdoc.fr/item/SJC_2008_2_1_a6/