An approach for certifying homotopy continuation paths: Univariate case

Juan Xu, Michael Burr, Chee Yap

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

Abstract

Homotopy continuation is a well-known method in numerical root-finding. Recently, certified algorithms for homotopy continuation based on Smale’s alpha-theory have been developed. This approach enforces very strong requirements at each step, leading to small step sizes. In this paper, we propose an approach that is independent of alpha-theory. It is based on the weaker notion of well-isolated approximations to the roots. We apply it to univariate polynomials and provide experimental evidence of its feasibility.

Original languageEnglish (US)
Title of host publicationISSAC 2018 - Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation
PublisherAssociation for Computing Machinery
Pages399-406
Number of pages8
ISBN (Electronic)9781450355506
DOIs
StatePublished - Jul 11 2018
Event43rd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2018 - New York, United States
Duration: Jul 16 2018Jul 19 2018

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Other

Other43rd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2018
CountryUnited States
CityNew York
Period7/16/187/19/18

Keywords

  • Certified Computation
  • Homotopy Continuation
  • Interval Arithmetic
  • Well-Isolated Roots

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'An approach for certifying homotopy continuation paths: Univariate case'. Together they form a unique fingerprint.

  • Cite this

    Xu, J., Burr, M., & Yap, C. (2018). An approach for certifying homotopy continuation paths: Univariate case. In ISSAC 2018 - Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (pp. 399-406). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). Association for Computing Machinery. https://doi.org/10.1145/3208976.3209010