Abstract
Functional iterations such as Newton’s are a popular tool for polynomial root-finding. We consider realistic situation where some (e.g., better-conditioned) roots have already been approximated and where further computations is directed to the approximation of the remaining roots. Such a situation is also realistic for root by means of subdivision iterations. A natural approach of applying explicit deflation has been much studied and recently advanced by one of the authors of this paper, but presently we consider the alternative of implicit deflation combined with the mapping of the variable and reversion of an input polynomial. We also show another unexplored direction for substantial further progress in this long and extensively studied area. Namely we dramatically increase the local efficiency of root-finding by means of the incorporation of fast algorithms for multipoint polynomial evaluation and Fast Multipole Method.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This set is universal for all polynomials p(x) that have all roots lying in the unit disc \(D(0,1)=\{z:~|z|=1\}\). Given any polynomial p(x) one can move all its roots into this disc by means of first readily computing a reasonably close upper bound on the absolute values of all roots and then properly shifting and scaling the variable x.
References
Aberth, O.: Iteration methods for finding all zeros of a polynomial simultaneously. Math. Comput. 27(122), 339–344 (1973)
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, New York (1998). https://doi.org/10.1007/978-1-4612-0701-6
Bini, D.A., Fiorentino, G.: Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numer. Algorithms 23, 127–173 (2000)
Bini, D.A., Robol, L.: Solving secular and polynomial equations: a multiprecision algorithm. J. Comput. Appl. Math. 272, 276–292 (2014)
Becker, R., Sagraloff, M., Sharma, V., Yap, C.: A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration. J. Symb. Comput. 86, 51–96 (2018)
Barba, L.A., Yokota, R.: How will the fast multipole method fare in Exascale Era? SIAM News 46(6), 1–3 (2013)
Durand, E.: Solutions numériques des équations algébriques, Tome 1: Equations du type F(X)=0. Racines d’un polynôme. Masson, Paris (1960)
Delves, L.M., Lyness, J.N.: A numerical method for locating the zeros of an analytic function. Math. Comput. 21, 543–560 (1967). https://doi.org/10.1090/S0025-5718-1967-0228165-4
Ehrlich, L.W.: A modified Newton method for polynomials. Commun. ACM 10, 107–108 (1967)
Hazewinkel, M. (ed.) Encyclopedia of Mathematics. Newton method. Springer Science+Business Media B.V. Kluwer Academic Publishers (1994, first edition), (2000, second edition). ISBN 978-1-55608-010-4
Gerasoulis, A., Grigoriadis, M.D., Sun, L.: A fast algorithm for Trummer’s problem. SIAM J. Sci. Stat. Comput. 8(1), 135–138 (1987)
Greengard, L., Rokhlin, V.: A fast algorithm for particle simulation. J. Comput. Phys. 73, 325–348 (1987)
Householder, A.S.: Dandelin, Lobachevskii, or Graeffe? Am. Math. Monthly 66, 464–466 (1959)
Henrici, P.: Applied and Computational Complex Analysis. Vol. 1: Power Series, Integration, Conformal Mapping, Location of Zeros. Wiley, New York (1974)
Henrici, P., Gargantini, I.: Uniformly convergent algorithms for the simultaneous approximation of all zeros of a polynomial. In: Dejon, B., Henrici, P. (eds.) Constructive Aspects of the Fundamental Theorem of Algebra. Wiley, New York (1969)
Habbard, J., Schleicher, D., Sutherland, S.: How to find all roots of complex polynomials by Newton’s method. Invent. Math. 146, 1–33 (2001)
Imbach, R., Pan, V.Y., Yap, C.: Implementation of a near-optimal complex root clustering algorithm. In: Davenport, J.H., Kauers, M., Labahn, G., Urban, J. (eds.) ICMS 2018. LNCS, vol. 10931, pp. 235–244. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96418-8_28
Kerner, I.O.: Ein Gesamtschrittverfahren zur Berechung der Nullstellen von Polynomen. Numerische Math. 8, 290–294 (1966)
Kirrinnis, P.: Polynomial factorization and partial fraction decomposition by simultaneous Newton’s iteration. J. Complex. 14, 378–444 (1998)
Kim, M.-H., Sutherland, S.: Polynomial root-finding algorithms and branched covers. SIAM J. Comput. 23(2), 415–436 (1994). https://doi.org/10.1137/S0097539791201587
Mahley, H.: Zur Auflösung Algebraisher Gleichngen. Z. Andew. Math. Physik. 5, 260–263 (1954)
McNamee, J.M.: Numerical Methods for Roots of Polynomials, Part I, XIX+354 pages. Elsevier (2007)
Moenck, R., Borodin, A.: Fast modular transforms via division. In: Proceedings of 13th Annual Symposium on Switching and Automata Theory (SWAT 1972), pp. 90–96. IEEE Computer Society Press (1972)
Mourrain, B., Pan, V.Y.: Lifting/descending processes for polynomial zeros and applications. J. Complex. 16(1), 265–273 (2000)
McNamee, J.M., Pan, V.Y.: Numerical Methods for Roots of Polynomials, Part II, XXI+728 pages. Elsevier (2013)
Ostrowski, A.M.: Solution of Equations and Systems of Equations. Academic Press, New York (1966)
Pan, V.Y.: Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC 1995), pp. 741–750. ACM Press, New York (1995)
Pan, V.Y.: Approximation of complex polynomial zeros: modified quadtree (Weyl’s) construction and improved Newton’s iteration. J. Complex. 16(1), 213–264 (2000)
Pan, V.Y.: Structured Matrices and Polynomials: Unified Superfast Algorithms. Springer, New York (2001). https://doi.org/10.1007/978-1-4612-0129-8
Pan, V.Y.: Univariate polynomials: nearly optimal algorithms for factorization and rootfinding. J. Symb. Comput. 33(5), 701–733 (2002)
Pan, V.Y.: Transformations of matrix structures work again. Linear Algebra Appl. 465, 1–32 (2015)
Pan, V.Y.: Simple and nearly optimal polynomial root-finding by means of root radii approximation. In: Kotsireas, I.S., Martinez-Moro, E. (eds.) ACA 2015. Springer Proceedings in Mathematics and Statistics, Ch. 23: Applications of Computer Algebra, vol. 198, pp. 329–340. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-56932-1_23
Pan, V.Y.: Old and new nearly optimal polynomial root-finders. In: CASC (2019). arxiv:1805.12042 [cs.NA], May 2019
Renegar, J.: On the worst-case arithmetic complexity of approximating zeros of polynomials. J. Complex. 3(2), 90–113 (1987)
Schönhage, A.: The fundamental theorem of algebra in terms of computational complexity. Technical report, Math. Dept., University of Tübingen, Tübingen, Germany (1982)
Schleicher, D., Stoll, R.: Newton’s method in practice: finding all roots of polynomials of degree one million efficiently. Theor. Comput. Sci. 681, 146–166 (2017)
Tilli, P.: Convergence conditions of some methods for the simultaneous computation of polynomial zeros. Calcolo 35, 3–15 (1998)
Weierstrass, K.: Neuer Beweis des Fundamentalsatzes der Algebra. Mathematische Werker, Tome III, pp. 251–269. Mayer und Mueller, Berlin (1903)
Weyl, H.: Randbemerkungen zu Hauptproblemen der Mathematik. II. Fundamentalsatz der Algebra and Grundlagen der Mathematik. Mathematische Zeitschrift 20, 131–151 (1924)
Werner, W.: Some improvements of classical iterative methods for the solution of nonlinear equations. In: Allgower, E.L., Glashoff, K., Peitgen, H.-O. (eds.) Numerical Solution of Nonlinear Equations. LNM, vol. 878, pp. 426–440. Springer, Heidelberg (1981). https://doi.org/10.1007/BFb0090691
Acknowledgements
The research of R. Inbach, V. Y. Pan, C. Yap, and V. Zaderman was supported by NSF Grant CCF–1563942. The research of V. Y. Pan and V. Zaderman was also supported by NSF Grants CCF 1116736 and PSC CUNY Award 69813 00 48. The research of Ilias Kotsireas was supported by an NSERC grant.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Imbach, R., Pan, V.Y., Yap, C., Kotsireas, I.S., Zaderman, V. (2019). Root-Finding with Implicit Deflation. In: England, M., Koepf, W., Sadykov, T., Seiler, W., Vorozhtsov, E. (eds) Computer Algebra in Scientific Computing. CASC 2019. Lecture Notes in Computer Science(), vol 11661. Springer, Cham. https://doi.org/10.1007/978-3-030-26831-2_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-26831-2_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-26830-5
Online ISBN: 978-3-030-26831-2
eBook Packages: Computer ScienceComputer Science (R0)