Polynomial root finding using iterated Eigenvalue computation

ABSTRACT

We analyze an iterative algorithm that approximates all roots of a univariate polynomial. The algorithm is based on (hardware) floating-point eigenvalue computation of a generalized companion matrix. With some assumptions, we show that it approximates the roots to floating-point accuracy within about log&rgr;/e X(P) iterations, where ∈ is the relative error of floating-point arithmetic, &rgr; is the relative separation of the roots, and X(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 floating-point accuracy at n points. On some hard examples of ill-conditioned polynomials, e.g. high-degree Wilkinson polynomials, the algorithm is an order of magnitude faster than the best alternative.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: D.H. Bailey, A portable high performance multiprecision package, RNR Technical report RNR-90-022, NAS Applied Research Branch, NASA Ames Research Center.
• 3: D.A. Bini, G. Fiorentino, Design, analysis, and implementation of a multiprecision polynomial rootfinder, Numerical Algorithms, 23:127-173, 2000.
• 4: D.A. Bini, G. Fiorentino, Numerical computation of polynomial roots using MPSolve, manuscript, 1999. Software and paper available for download from ftp ://ftp. dm. unipi, it/pub/mpsolve/.
• 5: J. W. Demmel, On condition numbers and the distance to the nearest III-posted problem, Numerische Mathematik, v.51 n.3, p.251-289, July 1987 [doi>10.1007/BF01400115]
• 6: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 7: Alan Edelman , H. Murakami, Polynomial roots from companion matrix eigenvalues, Mathematics of Computation, v.64 n.210, p.763-776, April 1995 [doi>10.2307/2153450]
• 8: L. Elsner, A remark on simultaneous inclusions of the zeros of a polynomial by Gershgorin's theorem, Numer. Math., 21:425-427, 1973.
• 9: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 10: X. Gourdon, Combinatoire, Algorithmique et Gomdtrie des Polyndmes, Ph.D. thesis, L'tcole Polytechnique, 1996, available at pauillac, inria, fr/algo/gourdon/.
• 11: T. Granlund, GNU MP: the GNU multiple precision arithmetic library, Edition 2.0, 1996. Code available for download from ww. swox. com/gmp/.
• 12: F. Malek, R. Vaillancourt, A composite polynomial zerofinding matrix algorithm, Computers Math. Applie. 30(2):37-47, 1995.
• 13: Brian T. Smith, Error Bounds for Zeros of a Polynomial Based Upon Gerschgorin's Theorems, Journal of the ACM (JACM), v.17 n.4, p.661-674, Oct. 1970 [doi>10.1145/321607.321615]
• 14: B.T. Smith, J.M. Boyle, J.J. Dongarra, B.S. Garbow, Y. Ikebe, V.C. Klema, C.B. Moler, Matrix Eigensystem Routines - EISPACK Guide, volume 6 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1976. Source code is available from netlib at www. netlib, org.
• 15: Peter Henrici, Applied and computational complex analysis. Vol. 3: discrete Fourier analysis—Cauchy integrals—construction of conformal maps---univalent functions, John Wiley & Sons, Inc., New York, NY, 1986
• 16: John Michael McNamee, A bibliography on roots of polynomials, Journal of Computational and Applied Mathematics, v.47 n.3, p.391-394, Sept. 30, 1993 [doi>10.1016/0377-0427(93)90064-I]
• 17: Victor Y. Pan, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Review, v.39 n.2, p.187-220, June 1997 [doi>10.1137/S0036144595288554]
• 18: P. Tilli, Convergence conditions of some methods for the simultaneous computation of polynomial zeroes, Calcolo 35:3-15, 1998.
• 19: P. Van Dooren, P. Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Lin. Alg. Appl, 50:545-579, 1983.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

General Terms:
Algorithms, Measurement, Performance, Verification