Polynomial Root-Finding by Exploiting Matrix Structure and the Eigenvectors.

Victor Pan

Department of Mathematics and Computer Science
Lehman College of CUNY, Bronx, NY 10468, USA.


To refine crude initial approximations to the roots of a univariate polynomial, we exploit the structure of the associated generalized companion matrix and the correlation between its eigenvalues and eigenvectors. This leads us to a new derivation of the Weierstrass (Durand--Kerner) algorithm for polynomial root-finding and to new root--finders having cubic and quartic orders of convergence. Furthermore, we modify the Weierstrass algorithm to decrease its computational precision dramatically, still preserving its quadratic convergence and using about as many flops per an iteration step. Practical promise of this modification is accentuated further because its every step essentially amounts to multiplication of three Cauchy matrices by three vectors (which generalizes Trummer's problem); application of the Fast Multipole algorithm should further accelerate the computations. Our other iterative algorithms are also reduced to similar computations with (generalized) Cauchy matrices. The power of our approach is enhanced by involving the shifted inverse power iteration and effective techniques for computing the initial approximation to the roots.