Adaptive Step Size Control for Polynomial Homotopy Continuation Methods

Sascha Timme

Contact the author: Please use for correspondence this email.
Submission date: 12. Feb. 2019
Pages: 16
Bibtex
Download full preprint: PDF (346 kB)
Link to arXiv: See the arXiv entry of this preprint.

Abstract:
In this paper we develop an adaptive step size control for the numerical tracking of implicitly defined paths in the context of polynomial homotopy continuation methods. We focus on the case where the paths are tracked using a predictor-corrector scheme with only a prescribed maximal number of allowed correction steps. The adaptive step size control changes the step size based on computational estimates of local geometric information, in particular a local Lipschitz constant and the local error of the used predictor method, as well as its order. The developed adaptive step size control is implemented in the software package HomotopyContinuation.jl and its efficiency over the currently commonly used adaptive step size control is demonstrated on several examples.