Old and new nearly optimal polynomial root-finders (Q2175594)

The paper is a great overview on problems related with the computational complexity of polynomial roots finding and polynomial factorization algorithms, tracking back to several important results available in the literature. Furthermore the author proposes new hybrid roots finders by means of an intelligent combination of known techniques. More precisely, some new roots finders based on an appropriate combination of Ehrlich's techniques for factorization and subdivision iterations are introduced. In the final sections the author proposes a new near-optimal linear segment polynomial finder. For the entire collection see [Zbl 1428.68016].