SIROCCO: A Library for Certified Polynomial Root Continuation

Marco-Buzunariz, M.A. (Universidad de Zaragoza) ; Rodriguez, M.

Resumen: The classical problem of studying the topology of a plane algebraic curve is typically handled by the computation of braid monodromies. The existence of arithmetic Zariski pairs implies that purely algebraic methods cannot provide those braids, so we need numerical methods at some point. However, numerical methods usually have the problem that floating point arithmetic introduces rounding errors that must be controlled to ensure certified results. We present SIROCCO (The source code and documentation is available in: https://github.com/miguelmarco/sirocco), a library for certified polynomial root continuation, specially suited for this task. It computes piecewise linear approximations of the paths followed by the roots. The library ensures that there exist disjoint tubular neighborhoods that contain both the actual path and the computed approximation. This fact proves that the braids corresponding to the approximation are equal to the ones corresponding to the actual curve. The validation is based on interval floating point arithmetic, the Interval Newton Criterion and auxiliary lemmas. We also provide a SageMath interface and auxiliary routines that perform all the needed pre and post- processing tasks. Together this is an "out of the box" solution to compute, for instance, the fundamental group of the complement of an affine complex curve.

Idioma: Inglés

DOI: 10.1007/978-3-319-42432-3_24

Año: 2016

Publicado en: Lecture Notes in Computer Science 9725 (2016), 191-197
ISSN: 0302-9743

Factor impacto SCIMAGO: 0.339 - Computer Science (miscellaneous) (Q2) - Theoretical Computer Science (Q3)

Tipo y forma: Article (PostPrint)

Área (Departamento): Área Didáctica Matemática (Dpto. Matemáticas)