PhD Defence: Symbolic-Numeric Algorithms for Plane Algebraic Curves

Symbolic-Numeric Algorithms for Plane Algebraic Curves

In computer algebra, the problem of computing topological invariants (i.e. delta-invariant, genus) of a plane complex algebraic curve is well-understood if the coefficients of the defining polynomial of the curve are exact data (i.e. integer or rational numbers). The challenge is to handle this problem if the coefficients are inexact (i.e. numerical values).

In this thesis, we approach the algebraic problem of computing topological invariants of a plane complex algebraic curve defined by a polynomial with both exact and inexact coefficients. For the inexact data, we associate a positive real number called tolerance or noise, which measures the error level in the coefficients. We deal with an ill-posed problem in the sense that, tiny changes in the input data lead to huge modifications in the output solution. For handling the ill-posedness of the problem we present a regularization method, which estimates the invariants of a plane complex algebraic curve. Our regularization method consists of a set of symbolic-numeric algorithms that extract structural information on the input curve, and of a parameter choice rule, i.e. a function in the noise level. We first design the symbolic-numeric algorithms for computing the invariants of a plane complex algebraic curve: (1) we compute the link of each singularity by numerical equation solving; (2) we compute the Alexander polynomial of each link by using algorithms from computational geometry and combinatorial objects from knot theory; (3) we derive formulas for the delta-invariant and for the genus. We then prove that the symbolic-numeric algorithms together with the parameter choice rule compute approximate solutions, which satisfy the convergence for noisy data property. Moreover, we perform several numerical experiments, which support the validity for the convergence statement.