Skip to main content
SpringerLink
Log in

Design, analysis, and implementation of a multiprecision polynomial rootfinder

  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

We present the design, analysis, and implementation of an algorithm for the computation of any number of digits of the roots of a polynomial with complex coefficients. The real and the imaginary parts of the coefficients may be integer, rational, or floating point numbers represented with an arbitrary number of digits. The algorithm has been designed to deal also with numerically hard polynomials like those arising from the symbolic preprocessing of systems of polynomial equations, where the degree and the size of the coefficients are typically huge.

The algorithm is based on an adaptive strategy which automatically exploits any specific feature of the input polynomial, like its sparsity or the conditioning of its roots, in order to speed up the computation. We introduce different concepts and tools suitably designed to arrive at an adaptive implementation, such as the concepts of ε‐root neighborhood, ε‐inclusion discs and some inclusion and conditioning theorems for their determination. The main engine for shrinking the inclusion discs is the simultaneous iteration method of Ehrlich–Aberth, complemented with a suitable technique for cluster analysis that is used for getting rid of the slow convergence in case of clustered or multiple roots.

The algorithm, implemented in C, relies on the GNU multiprecision package GMP and allows many options. Counting, isolating and approximating all roots in a given set \(\mathcal{S} \)are the main goals that the algorithm provides. Automatic determination of multiplicities and the detection of real or imaginary roots can be selected as well. Polynomials having coefficients with a bounded precision may be processed too. Comparisons with the polynomial rootfinders of the packages Mathematica™, Maple™and Pari, performed on a wide class of test polynomials show that our algorithm is generally much faster: in most cases the speed‐up factor is greater than 10 and, for certain polynomials, it is greater than 1000. The MPSolve package can be downloaded from the numeralgo library of netlib.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. O. Aberth, Iteration methods for finding all zeros of a polynomial simultaneously, Math. Comp. 27(122) (1973) 339-344.

    MATH  MathSciNet  Google Scholar 

  2. D.A. Adams, A stopping criterion for polynomial root finding, Comm. ACM 10 (1967) 655-658.

    MATH  MathSciNet  Google Scholar 

  3. D.H. Bailey, A Portable High Performance Multiprecision Package, RNR Technical Report RNR-90-022, NAS Applied Rsearch Branch, NASA Ames Research center, Moffet Field, CA.

  4. D. Bini and G. Fiorentino, Adaptive multiprecision algorithm for univariate polynomial zeros, in: Proc. of the 1st Internat. MATHEMATICA Sympos.(1995) pp. 53-60.

  5. D. Bini and G. Fiorentino, A multiprecision implementation of a poly-algorithm for univariate polynomial zeros, in: Proc. of the POSSO Workshop on Software(1995).

  6. D.A. Bini and G. Fiorentino, Mpsolve: Numerical computation of polynomial roots v2.0, FRISCO Technical Report (1998).

  7. D.A. Bini and G. Fiorentino, On the parallel evaluation of a sparse polynomial at a point, Numer. Algorithms 20(4) (1999) 323-329.

    MATH  MathSciNet  Google Scholar 

  8. D.A. Bini, Numerical computation of polynomial zeros by means of Aberth's method, Numer. Algorithms 13 (1996) 179-200.

    MATH  MathSciNet  Google Scholar 

  9. D. Bini and V. Pan, Polynomial and Matrix Computations, Vol. 1: Fundamental Algorithms, Progress in Theoretical Computer Science (Birkhäuser, Boston, 1994).

    Google Scholar 

  10. W. Börsch-Soupan, A-posteriori error bounds for the zeros of polynomials, Numer. Math. 5 (1963) 380-398.

    MathSciNet  Google Scholar 

  11. C. Carstensen, Inclusion of the roots of a polynomial based on Gerschgorin's theorem, Numer. Math. 59 (1991) 349-360.

    MATH  MathSciNet  Google Scholar 

  12. D. Coppersmith and C.A. Neff, Roots of a polynomial and its derivatives, in: Proc. of the 5th Annual ACM-SIAM Sympos. on Discrete Algorithms, Arlington, VA, USA (January 23-25, 1994) (ACM, New York, 1994) pp. 271-279.

    Google Scholar 

  13. E. Durand, Solutions Numériques des Equations Algébriques, Tome 1: Equations du Type F(X) = 0; Racines d'un Polynôme(Masson, Paris, 1960).

  14. L.W. Ehrlich, A modified Newton method for polynomials, Comm. ACM 10(2) (1967) 107-108.

    MATH  Google Scholar 

  15. L. Elsener, A remark on simultaneous inclusions of the zeros of a polynomial by Gerschgorin's theorem, Numer. Math. 21 (1973) 425-427.

    MathSciNet  Google Scholar 

  16. W. Gautschi, Questions of numerical condition related to polynomials, in: Recent Advances in Numerical Analysis, eds. C. de Boor and G.H. Golub (Academic Press, New York, 1978) pp. 45-72.

    Google Scholar 

  17. G.H. Golub and C.F. Van Loan, Matrix Computations(Johns Hopkins Univ. Press, Baltimore, MD, 1989).

    MATH  Google Scholar 

  18. X. Gourdon, Algorithmique du théorème fondamental de l'algébre, Rapport de Recherche No. 1852, INRIA (1993).

  19. T. Granlund, GNU MP: The GNU multiple precision arithmetic library, edition 2.0 (April 1996).

  20. H. Guggenheimer, Initial approximations in Durand-Kerner's root finding method, BIT 26 (1986) 537-539.

    MATH  Google Scholar 

  21. P. Henrici, Applied and Computational Complex Analysis, Vol. 1 (Wiley, New York, 1974).

    MATH  Google Scholar 

  22. M. Igarashi, A termination criterion for iterative methods used to find the zeros of polynomials, Math. Comp. 42 (1984) 165-171.

    MATH  MathSciNet  Google Scholar 

  23. B. Jackson, A zero-free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2(3) (1993) 325-336.

    Article  MATH  MathSciNet  Google Scholar 

  24. M.A. Jenkins and J.F. Traub, A three stage variable shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration, Numer. Math. 14 (1970) 252-263.

    MATH  MathSciNet  Google Scholar 

  25. I.O. Kerner, Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen, Numer. Math. 8 (1966) 290-294.

    MATH  MathSciNet  Google Scholar 

  26. P. Kirrinnis, Partial fraction decomposition in C(z) and simultaneous Newton iteration for factorization in C[z], J. Complexity 14 (1998) 378-444.

    MATH  MathSciNet  Google Scholar 

  27. P. Kirrinnis, Fast computation of contour integrals of rational functions, J. Complexity, to appear.

  28. W.S. Luk and T.C. Chen, Parallelizing a class of root finding methods by means of pseudo-deflation, Report, Department of Computer Science, The Chinese University of Hong Kong, Shatin, Hong Kong (1994).

    Google Scholar 

  29. K. Madsen and K. Reid, Fortran subroutines for finding polynomial zeros, Technical Report HL 75/1172(C.13), Computer Science and Systems Divisions, A.E.R.E. Harwell, Oxford (1975).

    Google Scholar 

  30. V.H. Maehly, Zur iterativen auflösing algebraischer gleichungen, Z. Angew. Math. Phys. 5 (1954) 260-263.

    MATH  MathSciNet  Google Scholar 

  31. J.M. McNamee, A bibliography on roots of polynomials, J. Comput. Appl. Math. 47 (1993) 391-394.

    MATH  MathSciNet  Google Scholar 

  32. J.M. McNamee, A comparison of methods for terminating polynomial iterations, J. Comput. Appl. Math. 21 (1998) 239-244.

    MathSciNet  Google Scholar 

  33. R.G. Mosier, Root neighborhoods of a polynomial, Math. Comp. 47 (1986) 265-273.

    MATH  MathSciNet  Google Scholar 

  34. A. Ostrowski, On a theorem by J.L. Walsh concerning the moduli of roots of algebraic equations, Bull. A.M.S. 47 (1941) 742-746.

    Article  MATH  MathSciNet  Google Scholar 

  35. V.Y. Pan, On approximating complex polynomial zeros: Modified quadtree (Weyl's) construction and improved Newton's iteration, in: 5th Annual ACM-SIAM Sympos. on Discrete Algorithms(ACM Press, New York, and SIAM, Philadelphia, PA, 1994).

    Google Scholar 

  36. V.Y. Pan, Sequential and parallel complexity of approximate evaluation of polynomial zeros, Comput. Math. Appl. 14(8) (1987) 591-622.

    MATH  MathSciNet  Google Scholar 

  37. V.Y. Pan, Solving a polynomial equation: Some history and recent progress, SIAM Rev. 39(2) (1997) 187-220.

    MATH  MathSciNet  Google Scholar 

  38. V.Y. Pan, Optimal and nearly optimal algorithms for approximating complex polynomial zeros, Comput. Math. Appl. 31 (1996) 97-138.

    MATH  Google Scholar 

  39. N. Psycharis, Analysis of the Lee-Yang zeros in lattice compact QED with scalars and fermions in 3D and in lattice noncompact QED in 4D, Ph.D. thesis, University of Glasgow (December 1998).

  40. J. Renegar, On the computational complexity of approximating solutions for real algebraic formulas, SIAM J. Comput. 21(6) (1992) 1008-1025.

    MATH  MathSciNet  Google Scholar 

  41. J. Renegar, On the worst case arithmetic complexity of approximating zeros of polynomials, J. Complexity 3 (1987) 90-113.

    MATH  MathSciNet  Google Scholar 

  42. F. Rouillier, Solving zero-dimensional systems through the rational univariate representation, Technical Report, Loria (to appear in Journal of AAECC).

  43. A. Schönhage, The fundamental theorem of algebra in terms of computational complexity, Technical Report, Mathematische Institut der Universität Tübingen (1982).

  44. B.T. Smith, Error bounds for the zeros of a polynomial based upon Gerschgorin's theorem, J. ACM 17 (1970) 661-674.

    MATH  Google Scholar 

  45. A. Sokal, personal communication (1999).

  46. H.J. Stetter, Analysis of zero cluster in multivariate polynomial systems, in: Proc. of ISSAC'96, ed. R. Caviness (1996) pp. 127-136.

  47. J. Stoer and R. Bulirsch, Introduction to Numerical Analysis(Springer, New York, 1980).

    Google Scholar 

  48. P. Tilli, Convergence conditions of some methods for the simultaneous computation of polynomial zeros, Calcolo 35(1) (1998) 3-15.

    MATH  MathSciNet  Google Scholar 

  49. J.H. Wilkinson, Practical problems arising in the solution of polynomial equations, J. Inst. Math. Appl. 8 (1971) 16-35.

    MATH  MathSciNet  Google Scholar 

Download references

Authors
  1. Dario Andrea Bini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giuseppe Fiorentino
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bini, D.A., Fiorentino, G. Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numerical Algorithms 23, 127–173 (2000). https://doi.org/10.1023/A:1019199917103

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1019199917103

Search

Navigation