Finding roots of univariate polynomials is one of the fundamental tasks of numerics, and there is still a wide gap between root finders that are well understood in theory and those that perform well in practice. We investigate the root-finding method of Weierstrass, also known as the Durand\u2013Kerner-method: this is a root finder that tries to approximate all roots of a given polynomial in parallel. This method has been introduced 130\u00a0years ago and has since then a good reputation for finding all roots in practice except in obvious cases of symmetry. Nonetheless, very little is known about its global dynamics and convergence properties.<\/p>\n
\n We show that the Weierstrass method, like the well-known Newton method, is not generally convergent: there are open sets of polynomials\u00a0\n \n We also establish another convergence problem for the Weierstrass method: for almost every polynomial of degree\n Our results are obtained by first interpreting the original problem coming from numerical mathematics in terms of higher-dimensional complex dynamics, then phrasing the question in algebraic terms in such a way that we could finally answer it by applying methods from computer algebra. The main innovation here is the translation into an algebraic question, which is amenable to (exact) computational methods close to the limits of current computer algebra systems.<\/p>","DOI":"10.1090\/mcom\/3783","type":"journal-article","created":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T10:32:59Z","timestamp":1663151579000},"page":"839-866","source":"Crossref","is-referenced-by-count":6,"title":["The Weierstrass\u2013Durand\u2013Kerner root finder is not generally convergent"],"prefix":"10.1090","volume":"92","author":[{"given":"Bernhard","family":"Reinke","sequence":"first","affiliation":[]},{"given":"Dierk","family":"Schleicher","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Stoll","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2022,11,10]]},"reference":[{"issue":"298","key":"1","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1090\/mcom\/2985","article-title":"On the speed of convergence of Newton\u2019s method for complex polynomials","volume":"85","author":"Bilarev, Todor","year":"2016","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"281","key":"2","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1090\/S0025-5718-2012-02640-8","article-title":"A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton\u2019s method","volume":"82","author":"Bollob\u00e1s, B\u00e9la","year":"2013","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3-4","key":"3","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","article-title":"The Magma algebra system. I. The user language","volume":"24","author":"Bosma, Wieb","year":"1997","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"4","first-page":"458","article-title":"HomotopyContinuation.jl: a package for homotopy continuation in Julia","author":"Breiding, Paul","year":"2018"},{"issue":"3","key":"5","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1088\/0951-7715\/16\/3\/312","article-title":"On K\u00f6nig\u2019s root-finding algorithms","volume":"16","author":"Buff, Xavier","year":"2003","journal-title":"Nonlinearity","ISSN":"https:\/\/id.crossref.org\/issn\/0951-7715","issn-type":"print"},{"key":"6","article-title":"Singular 4-1-2 \u2014 A computer algebra system for polynomial computations","author":"Decker, Wolfram","year":"2019"},{"key":"7","first-page":"136","article-title":"A variant of Newton\u2019s method for the simultaneous approximation of all roots of an algebraic equation","volume":"5(38)","author":"Do\u010dev, Kiril","year":"1962","journal-title":"Fiz.-Mat. Spis. B\\bud lgar. Akad. Nauk.","ISSN":"https:\/\/id.crossref.org\/issn\/0015-3265","issn-type":"print"},{"key":"8","volume-title":"Solutions num\\'{e}riques des \\'{e}quations alg\\'{e}briques. Tome I: \\'{E}quations du type $F(x)=0$; racines d'un polyn\\^{o}me","author":"Durand, E.","year":"1960"},{"key":"9","isbn-type":"print","first-page":"339","article-title":"On the iteration of entire functions","author":"Er\u00ebmenko, A. \u00c8.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/8301087005"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.17323\/1609-4514-2005-5-1-105-124","article-title":"Parametrizing unstable and very unstable manifolds","volume":"5","author":"Hubbard, John H.","year":"2005","journal-title":"Mosc. Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/1609-3321","issn-type":"print"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s002220100149","article-title":"How to find all roots of complex polynomials by Newton\u2019s method","volume":"146","author":"Hubbard, John","year":"2001","journal-title":"Invent. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-9910","issn-type":"print"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1145\/232826.232830","article-title":"The mathematical basis and a prototype implementation of a new polynomial rootfinder with quadratic convergence","volume":"22","author":"Hull, T. E.","year":"1996","journal-title":"ACM Trans. Math. Software","ISSN":"https:\/\/id.crossref.org\/issn\/0098-3500","issn-type":"print"},{"key":"13","isbn-type":"print","volume-title":"Polynomial root-finding and polynomiography","author":"Kalantari, Bahman","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9789812700599"},{"key":"14","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BF02162564","article-title":"Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen","volume":"8","author":"Kerner, Immo O.","year":"1966","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"3","key":"15","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/BF01446400","article-title":"Ueber eine Eigenschaft der Potenzreihen","volume":"23","author":"K\u00f6nig, Julius","year":"1884","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[LMS22] R. Lodge, Y. Mikulich, and D. Schleicher, A classification of postcritically finite Newton maps, In the Tradition of Thurston II: Geometry and Groups, 2022, pp. 421\u2013448, DOI 10.1007\/978-3-030-97560-9_13.","DOI":"10.1007\/978-3-030-97560-9_13"},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"467","DOI":"10.2307\/1971408","article-title":"Families of rational maps and iterative root-finding algorithms","volume":"125","author":"McMullen, Curt","year":"1987","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/S0377-0427(01)00546-5","article-title":"A 2002 update of the supplementary bibliography on roots of polynomials","volume":"142","author":"McNamee, John Michael","year":"2002","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"key":"19","series-title":"Studies in Computational Mathematics","isbn-type":"print","volume-title":"Numerical methods for roots of polynomials. Part I","volume":"14","author":"McNamee, J. M.","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9780444527295"},{"key":"20","series-title":"Studies in Computational Mathematics","isbn-type":"print","volume-title":"Numerical methods for roots of polynomials. Part II","volume":"16","author":"McNamee, J. M.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9780444527301"},{"key":"21","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-5703-5","volume-title":"Geometric theory of dynamical systems","author":"Palis, Jacob, Jr.","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/0387906681"},{"issue":"2","key":"22","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/S0036144595288554","article-title":"Solving a polynomial equation: some history and recent progress","volume":"39","author":"Pan, Victor Y.","year":"1997","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"5","key":"23","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1006\/jsco.2002.0531","article-title":"Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding","volume":"33","author":"Pan, Victor Y.","year":"2002","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"24","article-title":"New progress in polynomial root-finding","author":"Pan, Victor Y.","year":"2021"},{"issue":"8","key":"25","doi-asserted-by":"publisher","first-page":"1755","DOI":"10.1016\/j.cam.2009.09.012","article-title":"On Schr\u00f6der\u2019s families of root-finding methods","volume":"233","author":"Petkovi\u0107, M. S.","year":"2010","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"key":"26","article-title":"Newton\u2019s method in practice II: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees","author":"Randig, Marvin","year":"2017"},{"issue":"3","key":"27","doi-asserted-by":"publisher","first-page":"1287","DOI":"10.1090\/proc\/15715","article-title":"Diverging orbits for the Ehrlich-Aberth and the Weierstrass root finders","volume":"150","author":"Reinke, Bernhard","year":"2022","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"issue":"1","key":"28","doi-asserted-by":"publisher","first-page":"77","DOI":"10.4007\/annals.2011.173.1.3","article-title":"Dynamic rays of bounded-type entire functions","volume":"173","author":"Rottenfusser, G\u00fcnter","year":"2011","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"29","article-title":"On the Efficient Global Dynamics of Newton\u2019s Method for Complex Polynomials","author":"Schleicher, Dierk","year":"2016"},{"key":"30","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.tcs.2017.03.025","article-title":"Newton\u2019s method in practice: Finding all roots of polynomials of degree one million efficiently","volume":"681","author":"Schleicher, Dierk","year":"2017","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"2","key":"31","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/BF01444024","article-title":"Ueber unendlich viele Algorithmen zur Aufl\u00f6sung der Gleichungen","volume":"2","author":"Schr\u00f6der, E.","year":"1870","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"issue":"12","key":"32","doi-asserted-by":"publisher","first-page":"6945","DOI":"10.3934\/dcds.2020261","article-title":"Finding polynomial roots by dynamical systems\u2014a case study","volume":"40","author":"Shemyakov, Sergey","year":"2020","journal-title":"Discrete Contin. Dyn. Syst.","ISSN":"https:\/\/id.crossref.org\/issn\/1078-0947","issn-type":"print"},{"issue":"2","key":"33","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/S0273-0979-1985-15391-1","article-title":"On the efficiency of algorithms of analysis","volume":"13","author":"Smale, Steve","year":"1985","journal-title":"Bull. Amer. Math. Soc. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0273-0979","issn-type":"print"},{"key":"34","unstructured":"[Sto] M. Stoll, Magma code verifying the results in Sections \\ref{SS:perpts} and \\ref{Sec:Cubic}, \\url{http:\/\/www.mathe2.uni-bayreuth.de\/stoll\/magma\/index.html#Weierstrass}."},{"key":"35","first-page":"1085","article-title":"Neuer Beweis des Satzes, dass jede ganze rationale Function einer Ver\u00e4nderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Ver\u00e4nderlichen","author":"Weierstra\u00df, Karl","year":"1891","journal-title":"Sitzungsber.\\ K\\\"{o}niglich Preussischen Akad.\\ Wiss.\\ Berlin"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-340\/S0025-5718-2022-03783-2\/mcom3783_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-340\/S0025-5718-2022-03783-2\/S0025-5718-2022-03783-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:50:29Z","timestamp":1776833429000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-340\/S0025-5718-2022-03783-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,10]]},"references-count":35,"journal-issue":{"issue":"340","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["S0025-5718-2022-03783-2"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3783","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2022,11,10]]}}}