doi: 10.3934/dcds.2020261

Finding polynomial roots by dynamical systems – A case study

Institut de Mathématiques (UMR CNRS7373), Campus de Luminy 163 avenue de Luminy, Case 907 13288 Marseille 9, France

* Corresponding author: Sergey Shemyakov

Received  September 2019 Revised  March 2020 Published  July 2020

We investigate two well known dynamical systems that are designed to find roots of univariate polynomials by iteration: the methods known by Newton and by Ehrlich–Aberth. Both are known to have found all roots of high degree polynomials with good complexity. Our goal is to determine in which cases which of the two algorithms is more efficient. We come to the conclusion that Newton is faster when the polynomials are given by recursion so they can be evaluated in logarithmic time with respect to the degree, or when all the roots are all near the boundary of their convex hull. Conversely, Ehrlich–Aberth has the advantage when no fast evaluation of the polynomials is available, and when roots are in the interior of the convex hull of other roots.

Citation: Sergey Shemyakov, Roman Chernov, Dzmitry Rumiantsau, Dierk Schleicher, Simon Schmitt, Anton Shemyakov. Finding polynomial roots by dynamical systems – A case study. Discrete & Continuous Dynamical Systems - A, doi: 10.3934/dcds.2020261
References:
[1]

L. Arnold, Über die Nullstellenverteilung zufälliger Polynome, Math. Z., 92 (1966), 12-18.  doi: 10.1007/BF01140538.  Google Scholar

[2]

T. BilarevM. Aspenberg and D. Schleicher, On the speed of convergence of Newton's method for complex polynomials, Math. Comp., 85 (2016), 693-705.  doi: 10.1090/mcom/2985.  Google Scholar

[3]

D. A. Bini, Numerical computation of polynomial zeros by means of Aberth's method, Numer. Algorithms, 13 (1996), 179-200.  doi: 10.1007/BF02207694.  Google Scholar

[4]

D. A. Bini and G. Fiorentino, On the parallel evaluation of a sparse polynomial at a point, Numer. Algorithms, 20 (1999), 323-329.  doi: 10.1023/A:1019116203957.  Google Scholar

[5]

D. A. Bini and G. Fiorentino, Numerical computation of polynomials roots using MPSolve version 2.2, published online, 2000. Google Scholar

[6]

B. BollobásM. Lackmann and D. Schleicher, A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton's method, Math. Comp., 82 (2013), 443-457.  doi: 10.1090/S0025-5718-2012-02640-8.  Google Scholar

[7]

J. CarrierL. Greengard and V. Rokhlin, A fast adaptive multipole algorithm for particle simulations, SIAM J. Sci. Statist. Comput., 9 (1988), 669-686.  doi: 10.1137/0909044.  Google Scholar

[8]

A. Douady and J. H. Hubbard, Etude dynamique des polynômes complexes Ⅰ & Ⅱ, Publications Mathématiques d'Orsay, Université de Paris-Sud, Département de Mathématiques, Orsay, 1984.  Google Scholar

[9]

L. W. Ehrlich, A modified Newton method for polynomials, Comm. of ACM, 10 (1967), 107-108.  doi: 10.1145/363067.363115.  Google Scholar

[10]

P. Erdös and P. Turán, On the distribution of roots of polynomials, Ann. of Math., 51 (1950), 105-119.  doi: 10.2307/1969500.  Google Scholar

[11]

J. HubbardD. Schleicher and S. Sutherland, How to find all roots of complex polynomials with Newton's method, Invent. Math., 146 (2001), 1-33.  doi: 10.1007/s002220100149.  Google Scholar

[12]

R. Lodge, Y. Mikulich and D. Schleicher, A classification of postcritically finite Newton maps, preprint, (2015), arXiv: 1510.02771. Google Scholar

[13]

P. D. Proinov, Unified convergence analysis for Picard iteration in $n$-dimensional vector spaces, Calcolo, 55 (2018), Paper No. 6, 1–21. doi: 10.1007/s10092-018-0251-x.  Google Scholar

[14]

M. Randig, D. Schleicher and R. Stoll, Newton's method in practice Ⅱ: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees, preprint, (2019), arXiv: 1703.05847. doi: 10.1016/j.tcs.2017.03.025.  Google Scholar

[15]

B. Reinke, D. Schleicher and M. Stoll, The Weierstrass root finder is not generally convergent, preprint, arXiv: 2004.04777 Google Scholar

[16]

L. Robol, A Rootfinding Algorithm for Polynomials and Secular Equation, Master's thesis, University of Pisa, 2013. Google Scholar

[17]

D. Schleicher, On the efficient global dynamics of Newton's method for complex polynomials, preprint, arXiv: 1108.5773. Google Scholar

[18]

D. Schleicher, The Dynamics of Iterated Polynomials, work in progress. Google Scholar

[19]

D. Schleicher and R. Stoll, Newton's method in practice: Finding all roots of polynomials of degree one million efficiently, Theoret. Comput. Sci., 681 (2017), 146-166.  doi: 10.1016/j.tcs.2017.03.025.  Google Scholar

[20]

Sergey Shemyakov, Newton's Method for Complex Polynomials with Roots on a Unit Circle, Bachelor thesis, Jacobs University, 2018. Google Scholar

show all references

References:
[1]

L. Arnold, Über die Nullstellenverteilung zufälliger Polynome, Math. Z., 92 (1966), 12-18.  doi: 10.1007/BF01140538.  Google Scholar

[2]

T. BilarevM. Aspenberg and D. Schleicher, On the speed of convergence of Newton's method for complex polynomials, Math. Comp., 85 (2016), 693-705.  doi: 10.1090/mcom/2985.  Google Scholar

[3]

D. A. Bini, Numerical computation of polynomial zeros by means of Aberth's method, Numer. Algorithms, 13 (1996), 179-200.  doi: 10.1007/BF02207694.  Google Scholar

[4]

D. A. Bini and G. Fiorentino, On the parallel evaluation of a sparse polynomial at a point, Numer. Algorithms, 20 (1999), 323-329.  doi: 10.1023/A:1019116203957.  Google Scholar

[5]

D. A. Bini and G. Fiorentino, Numerical computation of polynomials roots using MPSolve version 2.2, published online, 2000. Google Scholar

[6]

B. BollobásM. Lackmann and D. Schleicher, A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton's method, Math. Comp., 82 (2013), 443-457.  doi: 10.1090/S0025-5718-2012-02640-8.  Google Scholar

[7]

J. CarrierL. Greengard and V. Rokhlin, A fast adaptive multipole algorithm for particle simulations, SIAM J. Sci. Statist. Comput., 9 (1988), 669-686.  doi: 10.1137/0909044.  Google Scholar

[8]

A. Douady and J. H. Hubbard, Etude dynamique des polynômes complexes Ⅰ & Ⅱ, Publications Mathématiques d'Orsay, Université de Paris-Sud, Département de Mathématiques, Orsay, 1984.  Google Scholar

[9]

L. W. Ehrlich, A modified Newton method for polynomials, Comm. of ACM, 10 (1967), 107-108.  doi: 10.1145/363067.363115.  Google Scholar

[10]

P. Erdös and P. Turán, On the distribution of roots of polynomials, Ann. of Math., 51 (1950), 105-119.  doi: 10.2307/1969500.  Google Scholar

[11]

J. HubbardD. Schleicher and S. Sutherland, How to find all roots of complex polynomials with Newton's method, Invent. Math., 146 (2001), 1-33.  doi: 10.1007/s002220100149.  Google Scholar

[12]

R. Lodge, Y. Mikulich and D. Schleicher, A classification of postcritically finite Newton maps, preprint, (2015), arXiv: 1510.02771. Google Scholar

[13]

P. D. Proinov, Unified convergence analysis for Picard iteration in $n$-dimensional vector spaces, Calcolo, 55 (2018), Paper No. 6, 1–21. doi: 10.1007/s10092-018-0251-x.  Google Scholar

[14]

M. Randig, D. Schleicher and R. Stoll, Newton's method in practice Ⅱ: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees, preprint, (2019), arXiv: 1703.05847. doi: 10.1016/j.tcs.2017.03.025.  Google Scholar

[15]

B. Reinke, D. Schleicher and M. Stoll, The Weierstrass root finder is not generally convergent, preprint, arXiv: 2004.04777 Google Scholar

[16]

L. Robol, A Rootfinding Algorithm for Polynomials and Secular Equation, Master's thesis, University of Pisa, 2013. Google Scholar

[17]

D. Schleicher, On the efficient global dynamics of Newton's method for complex polynomials, preprint, arXiv: 1108.5773. Google Scholar

[18]

D. Schleicher, The Dynamics of Iterated Polynomials, work in progress. Google Scholar

[19]

D. Schleicher and R. Stoll, Newton's method in practice: Finding all roots of polynomials of degree one million efficiently, Theoret. Comput. Sci., 681 (2017), 146-166.  doi: 10.1016/j.tcs.2017.03.025.  Google Scholar

[20]

Sergey Shemyakov, Newton's Method for Complex Polynomials with Roots on a Unit Circle, Bachelor thesis, Jacobs University, 2018. Google Scholar

Figure 1.  The Newton map for $ p(z) = z^3-2z+2 $ has a superattracting 2-cycle; the domain in black converges to this cycle
Figure 2.  Illustration of the "iterated refinement" idea: we start with a small number of points and refine when adjacent orbits no longer move in parallel. Note that most of the refinement happens once the orbits are close to the roots, which drastically reduces the necessary computations. Figure taken from [14]
Figure 3.  Complexity (in terms of arithmetic operations) for finding periodic points of quadratic polynomials; log-log scale. Top: the polynomial $ z^2+1 $; bottom: the polynomial $ z^2+i $. This graphs combine results for evaluating the polynomials in coefficient form ("slow evaluation") and evaluating using iteration ("fast evaluation"). Notice that for the Ehrlich–Aberth-iteration does not accelerate significantly by taking advantage of fast evaluation
Figure 4.  Complexity for finding centers of hyperbolic components of the Mandelbrot set; log-log scale
Figure 5.  Complexity for finding periodic points of Chebyshev polynomials; log-log scale. Top: evaluation of polynomials in coefficient form ("slow evaluation"); bottom: evaluation using iteration
Figure 6.  Complexity for finding roots of Legendre polynomials; log-log scale. Evaluated "slowly"
Figure 7.  Complexity for finding roots distributed randomly on the unit circle; log-log scale
Figure 8.  Complexity for finding roots distributed randomly in the unit disk; log-log scale
Figure 9.  Complexity for finding roots on a square grid; log-log scale
[1]

R. Baier, M. Dellnitz, M. Hessel-von Molo, S. Sertl, I. G. Kevrekidis. The computation of convex invariant sets via Newton's method. Journal of Computational Dynamics, 2014, 1 (1) : 39-69. doi: 10.3934/jcd.2014.1.39

[2]

Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143

[3]

Matthias Gerdts, Martin Kunkel. A nonsmooth Newton's method for discretized optimal control problems with state and control constraints. Journal of Industrial & Management Optimization, 2008, 4 (2) : 247-270. doi: 10.3934/jimo.2008.4.247

[4]

Andy M. Yip, Wei Zhu. A fast modified Newton's method for curvature based denoising of 1D signals. Inverse Problems & Imaging, 2013, 7 (3) : 1075-1097. doi: 10.3934/ipi.2013.7.1075

[5]

Henryk Leszczyński, Monika Wrzosek. Newton's method for nonlinear stochastic wave equations driven by one-dimensional Brownian motion. Mathematical Biosciences & Engineering, 2017, 14 (1) : 237-248. doi: 10.3934/mbe.2017015

[6]

Santanu Sarkar, Subhamoy Maitra. Some applications of lattice based root finding techniques. Advances in Mathematics of Communications, 2010, 4 (4) : 519-531. doi: 10.3934/amc.2010.4.519

[7]

T. Tachim Medjo. On the Newton method in robust control of fluid flow. Discrete & Continuous Dynamical Systems - A, 2003, 9 (5) : 1201-1222. doi: 10.3934/dcds.2003.9.1201

[8]

Xiaojiao Tong, Felix F. Wu, Yongping Zhang, Zheng Yan, Yixin Ni. A semismooth Newton method for solving optimal power flow. Journal of Industrial & Management Optimization, 2007, 3 (3) : 553-567. doi: 10.3934/jimo.2007.3.553

[9]

Zhi-Feng Pang, Yu-Fei Yang. Semismooth Newton method for minimization of the LLT model. Inverse Problems & Imaging, 2009, 3 (4) : 677-691. doi: 10.3934/ipi.2009.3.677

[10]

Masaru Ikehata. On finding the surface admittance of an obstacle via the time domain enclosure method. Inverse Problems & Imaging, 2019, 13 (2) : 263-284. doi: 10.3934/ipi.2019014

[11]

Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020139

[12]

Masaru Ikehata. On finding an obstacle with the Leontovich boundary condition via the time domain enclosure method. Inverse Problems & Imaging, 2017, 11 (1) : 99-123. doi: 10.3934/ipi.2017006

[13]

Masaru Ikehata, Mishio Kawashita. On finding a buried obstacle in a layered medium via the time domain enclosure method. Inverse Problems & Imaging, 2018, 12 (5) : 1173-1198. doi: 10.3934/ipi.2018049

[14]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237

[15]

Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235

[16]

Hans J. Wolters. A Newton-type method for computing best segment approximations. Communications on Pure & Applied Analysis, 2004, 3 (1) : 133-148. doi: 10.3934/cpaa.2004.3.133

[17]

Saeed Ketabchi, Hossein Moosaei, M. Parandegan, Hamidreza Navidi. Computing minimum norm solution of linear systems of equations by the generalized Newton method. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008

[18]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[19]

Mihaela Negreanu, J. Ignacio Tello. On a comparison method to reaction-diffusion systems and its applications to chemotaxis. Discrete & Continuous Dynamical Systems - B, 2013, 18 (10) : 2669-2688. doi: 10.3934/dcdsb.2013.18.2669

[20]

Jiawei Dou, Lan-sun Chen, Kaitai Li. A monotone-iterative method for finding periodic solutions of an impulsive competition system on tumor-normal cell interaction. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 555-562. doi: 10.3934/dcdsb.2004.4.555

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (22)
  • HTML views (60)
  • Cited by (0)

[Back to Top]