Geodesic
Nearly Optimal Algorithms for Univariate Polynomial Factorization and Rootfinding.~II: Computing a~Basic Annulus for Splitting
Informatics and Automation, Analytic and geometric issues of complex analysis, Tome 235 (2001), pp. 211-223

Voir la notice de l'article provenant de la source Math-Net.Ru

We describe some effective algorithms for the computation of a basic well isolated annulus over which we split a given univariate $n$th degree polynomial numerically into two factors. This is extended to recursive computation of the complete numerical factorization of a polynomial into the product of its linear factors and further to the approximation of its roots. The extension incorporates the earlier techniques of Schönhage and Kirrinnis and our old and new splitting techniques and yields nearly optimal (up to polylogarithmic factors) arithmetic and Boolean cost estimates for the complexity of both complete factorization and rootfinding. The improvement over our previous record Boolean complexity estimates is by roughly the factor of $n$ for complete factorization and also for the approximation of well-conditioned (well isolated) roots. 
@article{TRSPY_2001_235_a14,
     author = {V. Ya. Pan},
     title = {Nearly {Optimal} {Algorithms} for {Univariate} {Polynomial} {Factorization} and {Rootfinding.~II:} {Computing} {a~Basic} {Annulus} for {Splitting}},
     journal = {Informatics and Automation},
     pages = {211--223},
     publisher = {mathdoc},
     volume = {235},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TRSPY_2001_235_a14/}
}
TY  - JOUR
AU  - V. Ya. Pan
TI  - Nearly Optimal Algorithms for Univariate Polynomial Factorization and Rootfinding.~II: Computing a~Basic Annulus for Splitting
JO  - Informatics and Automation
PY  - 2001
SP  - 211
EP  - 223
VL  - 235
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TRSPY_2001_235_a14/
LA  - en
ID  - TRSPY_2001_235_a14
ER  - 
%0 Journal Article
%A V. Ya. Pan
%T Nearly Optimal Algorithms for Univariate Polynomial Factorization and Rootfinding.~II: Computing a~Basic Annulus for Splitting
%J Informatics and Automation
%D 2001
%P 211-223
%V 235
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TRSPY_2001_235_a14/
%G en
%F TRSPY_2001_235_a14
V. Ya. Pan. Nearly Optimal Algorithms for Univariate Polynomial Factorization and Rootfinding.~II: Computing a~Basic Annulus for Splitting. Informatics and Automation, Analytic and geometric issues of complex analysis, Tome 235 (2001), pp. 211-223. http://geodesic.mathdoc.fr/item/TRSPY_2001_235_a14/