Root-Finding with Implicit Deflation

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

doi:10.1007/978-3-030-26831-2_16

Root-Finding with Implicit Deflation

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Computer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings
Editors	Matthew England, Timur M. Sadykov, Werner M. Seiler, Wolfram Koepf, Evgenii V. Vorozhtsov
Publisher	Springer Verlag
Pages	236-245
Number of pages	10
ISBN (Print)	9783030268305
DOIs	https://doi.org/10.1007/978-3-030-26831-2_16
State	Published - 2019
Event	21st International Workshop on Computer Algebra in Scientific Computing, CASC 2019 - Moscow, Russian Federation Duration: Aug 26 2019 → Aug 30 2019

Publication series

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

Conference

Conference	21st International Workshop on Computer Algebra in Scientific Computing, CASC 2019
Country/Territory	Russian Federation
City	Moscow
Period	8/26/19 → 8/30/19

Keywords

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

Access to Document

10.1007/978-3-030-26831-2_16

Cite this

Imbach, R., Pan, V. Y., Yap, C., Kotsireas, I. S., & Zaderman, V. (2019). Root-Finding with Implicit Deflation. In M. England, T. M. Sadykov, W. M. Seiler, W. Koepf, & E. V. Vorozhtsov (Eds.), Computer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings (pp. 236-245). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11661 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-26831-2_16

Root-Finding with Implicit Deflation. / Imbach, Rémi; Pan, Victor Y.; Yap, Chee et al.
Computer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings. ed. / Matthew England; Timur M. Sadykov; Werner M. Seiler; Wolfram Koepf; Evgenii V. Vorozhtsov. Springer Verlag, 2019. p. 236-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11661 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Imbach, R, Pan, VY, Yap, C, Kotsireas, IS & Zaderman, V 2019, Root-Finding with Implicit Deflation. in M England, TM Sadykov, WM Seiler, W Koepf & EV Vorozhtsov (eds), Computer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11661 LNCS, Springer Verlag, pp. 236-245, 21st International Workshop on Computer Algebra in Scientific Computing, CASC 2019, Moscow, Russian Federation, 8/26/19. https://doi.org/10.1007/978-3-030-26831-2_16

Imbach R, Pan VY, Yap C, Kotsireas IS, Zaderman V. Root-Finding with Implicit Deflation. In England M, Sadykov TM, Seiler WM, Koepf W, Vorozhtsov EV, editors, Computer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings. Springer Verlag. 2019. p. 236-245. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-26831-2_16

Imbach, Rémi ; Pan, Victor Y. ; Yap, Chee et al. / Root-Finding with Implicit Deflation. Computer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings. editor / Matthew England ; Timur M. Sadykov ; Werner M. Seiler ; Wolfram Koepf ; Evgenii V. Vorozhtsov. Springer Verlag, 2019. pp. 236-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2c83731a1a73410890042beb2a78658a,

title = "Root-Finding with Implicit Deflation",

abstract = "Functional iterations such as Newton{\textquoteright}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.",

keywords = "Deflation, Efficiency, Ehrlich{\textquoteright}s iterations, Functional iterations, Maps of the variable, Newton{\textquoteright}s iterations, Polynomial roots, Taming wild roots, Weierstrass{\textquoteright}s iterations",

author = "R{\'e}mi Imbach and Pan, {Victor Y.} and Chee Yap and Kotsireas, {Ilias S.} and Vitaly Zaderman",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 21st International Workshop on Computer Algebra in Scientific Computing, CASC 2019 ; Conference date: 26-08-2019 Through 30-08-2019",

year = "2019",

doi = "10.1007/978-3-030-26831-2_16",

language = "English (US)",

isbn = "9783030268305",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "236--245",

editor = "Matthew England and Sadykov, {Timur M.} and Seiler, {Werner M.} and Wolfram Koepf and Vorozhtsov, {Evgenii V.}",

booktitle = "Computer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings",

}

TY - GEN

T1 - Root-Finding with Implicit Deflation

AU - Imbach, Rémi

AU - Pan, Victor Y.

AU - Yap, Chee

AU - Kotsireas, Ilias S.

AU - Zaderman, Vitaly

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Deflation

KW - Efficiency

KW - Ehrlich’s iterations

KW - Functional iterations

KW - Maps of the variable

KW - Newton’s iterations

KW - Polynomial roots

KW - Taming wild roots

KW - Weierstrass’s iterations

UR - http://www.scopus.com/inward/record.url?scp=85071504563&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071504563&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-26831-2_16

DO - 10.1007/978-3-030-26831-2_16

M3 - Conference contribution

AN - SCOPUS:85071504563

SN - 9783030268305

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 236

EP - 245

BT - Computer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings

A2 - England, Matthew

A2 - Sadykov, Timur M.

A2 - Seiler, Werner M.

A2 - Koepf, Wolfram

A2 - Vorozhtsov, Evgenii V.

PB - Springer Verlag

T2 - 21st International Workshop on Computer Algebra in Scientific Computing, CASC 2019

Y2 - 26 August 2019 through 30 August 2019

ER -

Root-Finding with Implicit Deflation

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this