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 and 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. |
| [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. |
| [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 |
| [16] |
L. Robol, A Rootfinding Algorithm for Polynomials and Secular Equation, Master's thesis, University of Pisa, 2013. |
| [17] |
D. Schleicher, On the efficient global dynamics of Newton's method for complex polynomials, preprint, arXiv: 1108.5773. |
| [18] |
D. Schleicher, The Dynamics of Iterated Polynomials, work in progress. |
| [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. |
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. |
| [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. |
| [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 |
| [16] |
L. Robol, A Rootfinding Algorithm for Polynomials and Secular Equation, Master's thesis, University of Pisa, 2013. |
| [17] |
D. Schleicher, On the efficient global dynamics of Newton's method for complex polynomials, preprint, arXiv: 1108.5773. |
| [18] |
D. Schleicher, The Dynamics of Iterated Polynomials, work in progress. |
| [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. |
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 and 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 and 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 and Imaging, 2013, 7 (3) : 1075-1097. doi: 10.3934/ipi.2013.7.1075 |
| [6] |
Suhua Wang, Zhiqiang Ma, Hongjie Ji, Tong Liu, Anqi Chen, Dawei Zhao. Personalized exercise recommendation method based on causal deep learning: Experiments and implications. STEM Education, 2022, 2 (2) : 157-172. doi: 10.3934/steme.2022011 |
| [7] |
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 |
| [8] |
T. Tachim Medjo. On the Newton method in robust control of fluid flow. Discrete and Continuous Dynamical Systems, 2003, 9 (5) : 1201-1222. doi: 10.3934/dcds.2003.9.1201 |
| [9] |
Xiaojiao Tong, Felix F. Wu, Yongping Zhang, Zheng Yan, Yixin Ni. A semismooth Newton method for solving optimal power flow. Journal of Industrial and Management Optimization, 2007, 3 (3) : 553-567. doi: 10.3934/jimo.2007.3.553 |
| [10] |
Zhi-Feng Pang, Yu-Fei Yang. Semismooth Newton method for minimization of the LLT model. Inverse Problems and Imaging, 2009, 3 (4) : 677-691. doi: 10.3934/ipi.2009.3.677 |
| [11] |
Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete and Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139 |
| [12] |
Masaru Ikehata. On finding the surface admittance of an obstacle via the time domain enclosure method. Inverse Problems and Imaging, 2019, 13 (2) : 263-284. doi: 10.3934/ipi.2019014 |
| [13] |
Masaru Ikehata. On finding an obstacle with the Leontovich boundary condition via the time domain enclosure method. Inverse Problems and Imaging, 2017, 11 (1) : 99-123. doi: 10.3934/ipi.2017006 |
| [14] |
Masaru Ikehata, Mishio Kawashita. On finding a buried obstacle in a layered medium via the time domain enclosure method. Inverse Problems and Imaging, 2018, 12 (5) : 1173-1198. doi: 10.3934/ipi.2018049 |
| [15] |
Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237 |
| [16] |
Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235 |
| [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 and Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008 |
| [18] |
Hans J. Wolters. A Newton-type method for computing best segment approximations. Communications on Pure and Applied Analysis, 2004, 3 (1) : 133-149 . doi: 10.3934/cpaa.2004.3.133 |
| [19] |
Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733 |
| [20] |
Hong-Yi Miao, Li Wang. Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 677-685. doi: 10.3934/naco.2021012 |
2021 Impact Factor: 1.588
Tools
Metrics
Other articles
by authors
[Back to Top]