Empirical study of an evaluation-based subdivision algorithm for complex root isolation

Narayan Kamath, Irina Voiculescu, Chee K. Yap

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

Abstract

We provide an empirical study of subdivision algorithms for isolating the simple roots of a polynomial in any desired box region B 0 of the complex plane. One such class of algorithms is based on Newton-like interval methods (Moore, Krawczyk, Hansen-Sengupta). Another class of subdivision algorithms is based on function evaluation. Here, Yakoubsohn discussed a method that is purely based on an exclusion predicate. Recently, Sagraloff and Yap introduced another algorithm of this type, called Ceval. We describe the first implementation of Ceval in Core Library. We compare its performance to the above mentioned algorithms, and also to the well-known MPSolve software from Bini and Florentino. Our results suggest that certified evaluation-based methods such as Ceval are encouraging and deserve further exploration.

Original languageEnglish (US)
Title of host publicationSNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation
Pages155-164
Number of pages10
DOIs
StatePublished - 2011
EventSNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation - San Jose, CA, United States
Duration: Jun 7 2011Jun 9 2011

Publication series

NameSNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation

Other

OtherSNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation
CountryUnited States
CitySan Jose, CA
Period6/7/116/9/11

Keywords

  • Ceval algorithm interval Newton methods
  • Complex root isolation
  • Solving bi-variate systems
  • Subdivision algorithms

ASJC Scopus subject areas

  • Modeling and Simulation

Fingerprint Dive into the research topics of 'Empirical study of an evaluation-based subdivision algorithm for complex root isolation'. Together they form a unique fingerprint.

  • Cite this

    Kamath, N., Voiculescu, I., & Yap, C. K. (2011). Empirical study of an evaluation-based subdivision algorithm for complex root isolation. In SNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation (pp. 155-164). (SNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation). https://doi.org/10.1145/2331684.2331710