Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding

摘要

To approximate all roots(zeros)of a univariate polynomials, we develop two effective algorithms and combine them in a single recursive process. One algorithm computes a basic well isolated zero-free annulus on the complex plane, whereas another algorithm numerically splits the input polynomial of the nth degree into two factors balanced in the degrees and with the zero sets separated by the basic annulus. Recursive combination of the two algorithms leads to computation of complete numerical factorization of a polynomial into the product of linear factors and further to the approximation of the roots.