Root-finding with implicit deflation

DOI10.1007/978-3-030-26831-2_16MaRDI QIDQ2175580zbMATH OpenOpenAlexFDO

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

Publication date 29 April 2020

Full work available at URL https://arxiv.org/abs/1606.01396

zbMATH Keywords

deflationefficiencyEhrlich's iterationsfunctional iterationsNewton's iterationspolynomial rootstaming wild rootsWeierstrass's iterations

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of roots of polynomial equations (65H04) Numerical computation of solutions to single equations (65H05)

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 approximation of the remaining roots. Such situation is also realistic for root-finding by means of subdivision. 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 contribute to the alternative approach of applying implicit deflation, which we combine with mapping 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 their local efficiency by means of the incorporation of fast algorithms for multipoint polynomial evaluation and Fast Multipole Method.

Review text

The authors consider a root-finding problem when some roots are already known approximately and the other ones have to be determined. An implicit deflation method combined with other techniques allow the authors to solve the problem. The local efficiency of the root-finding device is discussed. For the entire collection see [Zbl 1428.68016].

Recommendations

• Finding roots by deflated polynomial approximation
• scientific article; zbMATH DE number 794403
• Newton's method in practice: finding all roots of polynomials of degree one million efficiently
• A Rapid Robust Rootfinder
• Newton's method with deflation for isolated singularities of polynomial systems

Cited in

(2)

• Root-finding by expansion with independent constraints
• Finding imaginary roots using inners

This page was built for publication: Root-finding with implicit deflation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175580)