Certified Complex Numerical Root Finding

For root solving over the field of complex numbers, numerical methods are the de facto standard.
They are known to be reliable, highly efficient, and apply to a broad range of different input types. Unfortunately, most of the existing solvers fail to provide guarantees on the correctness of their output.
We present ARCaVoID, a highly generic and fast numerical Las Vegas-algorithm. It uses the well-established Aberth-Ehrlich simultaneous root finding iteration. Certificate on the exactness of the results are provided by rigorous application of interval arithmetics. Our implementation transparently handles the case of bitstream coefficients that can be approximated to any arbitrary precision, but cannot be represented exactly as rational numbers.

ARCaVoID is implemented in the C++ Computational Geometry Algorithms Library (CGAL), where it is used for bivariate system solving over the real numbers. The extended view including global information over the complex numbers, together with fast symbolic operations on the GPU, turns out to give a huge benefit over existing approaches.


In this talk, I will present the work done for my Master's thesis, advised by Michael Sagraloff. At the same time, it is a rehearsal talk for my application as a PhD student in AG1.