Newtonian Graphs, Riemann Surfaces and Computation

Abstract

In this thesis we study the Newtonian graph and how to compute it. We show different applications of this computation, ranging from numerical root finding to computing the genera of algebraic Riemann surfaces.

Newton's method in the complex plane gives rise to a vector field. Certain curves of flow in this field are of particular interest as they form a connected graph, the Newtonian graph. The faces of the graph are regions corresponding to roots of the input function, and Newton's method on each region "should" converge to that root. We give a symbolic algorithm to compute the Newtonian graph for rational functions. The resulting structure can be used to improve Newton's method to guarantee convergence.

We also show how to extend the notion of Newtonian flow to a Riemann surface of an algebraic function. Again we obtain a Newtonian graph, now living on the abstract Riemann surface. We show how the graph is a tiling of the surface, and can therefore be used to compute the genus of the surface. Then we extend our earlier graph computation to cover the algebraic functions as well. All this computation is very efficient in the sense that it can all be done within the NC complexity class. This gives the first NC algorithm to compute the genus of algebraic Riemann surfaces.