An Iterated Eigenvalue Algorithm for Approximating Roots of Univariate Polynomials

✍ Scribed by Steven Fortune

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 655 KB
• Volume: 33
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.2002.0526

✦ Synopsis

We discuss an iterative algorithm that approximates all roots of a univariate polynomial. The iteration is based on floating-point computation of the eigenvalues of a generalized companion matrix. With some assumptions, we show that the algorithm approximates the roots within about log ρ/ χ(P ) iterations, where is the relative error of floatingpoint arithmetic, ρ is the relative separation of the roots, and χ(P ) is the condition number of the polynomial. Each iteration requires an n × n floating-point eigenvalue computation, n the polynomial degree, and evaluation of the polynomial to floatingpoint accuracy at up to n points.

We describe a careful implementation of the algorithm, including many techniques that contribute to the practical efficiency of the algorithm. On some hard examples of ill-conditioned polynomials, e.g. high-degree Wilkinson polynomials, the implementation is an order of magnitude faster than the Bini-Fiorentino implementation mpsolve.