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
-
Previous Article
Interval homeomorphic solutions of a functional equation of nonautonomous iterations
- DCDS Home
- This Issue
-
Next Article
Euler integral and perihelion librations
December
2020, 40(12): 6945-6965.
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 |
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.
Keywords:
Root finding,
experiments,
polynomials,
efficiency,
Newton's method,
Ehrlich-Aberth method,
comparison.
Mathematics Subject Classification:
Primary: 49M15, 37F10, 37N30; Secondary: 65H04, 65-04, 65-05.
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,
2020, 40
(12)
: 6945-6965.
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. |
| [2] |
T. Bilarev, M. 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. |
| [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. |
| [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. |
| [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ás, M. 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. |
| [7] |
J. Carrier, L. 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. |
| [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. |
| [9] |
L. W. Ehrlich,
A modified Newton method for polynomials, Comm. of ACM, 10 (1967), 107-108.
doi: 10.1145/363067.363115. |
| [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. |
| [11] |
J. Hubbard, D. 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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [2] |
T. Bilarev, M. 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. |
| [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. |
| [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. |
| [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ás, M. 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. |
| [7] |
J. Carrier, L. 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. |
| [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. |
| [9] |
L. W. Ehrlich,
A modified Newton method for polynomials, Comm. of ACM, 10 (1967), 107-108.
doi: 10.1145/363067.363115. |
| [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. |
| [11] |
J. Hubbard, D. 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. |
| [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. |
| [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. |
| [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. |
| [20] |
Sergey Shemyakov, Newton's Method for Complex Polynomials with Roots on a Unit Circle, Bachelor thesis, Jacobs University, 2018. Google Scholar |
14]">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] |
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 |
| [5] |
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 |
| [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, 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] |
Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139 |
| [11] |
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 |
| [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] |
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 |
| [17] |
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 |
| [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] |
Hong-Yi Miao, Li Wang. Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 677-685. doi: 10.3934/naco.2021012 |
| [20] |
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 |
2020 Impact Factor: 1.392
Tools
Metrics
Other articles
by authors
[Back to Top]