Root-Finding with Implicit Deflation

Rémi Imbach, Victor Y. Pan, Chee Yap, Ilias S. Kotsireas, Vitaly Zaderman

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationComputer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings
EditorsMatthew England, Timur M. Sadykov, Werner M. Seiler, Wolfram Koepf, Evgenii V. Vorozhtsov
PublisherSpringer Verlag
Number of pages10
ISBN (Print)9783030268305
StatePublished - 2019
Event21st International Workshop on Computer Algebra in Scientific Computing, CASC 2019 - Moscow, Russian Federation
Duration: Aug 26 2019Aug 30 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11661 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International Workshop on Computer Algebra in Scientific Computing, CASC 2019
Country/TerritoryRussian Federation


  • Deflation
  • Efficiency
  • Ehrlich’s iterations
  • Functional iterations
  • Maps of the variable
  • Newton’s iterations
  • Polynomial roots
  • Taming wild roots
  • Weierstrass’s iterations

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Root-Finding with Implicit Deflation'. Together they form a unique fingerprint.

Cite this