dc.contributor.author Stefansson, Kjartan en_US dc.date.accessioned 2007-04-23T18:02:39Z dc.date.available 2007-04-23T18:02:39Z dc.date.issued 1995-05 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR95-1519 en_US dc.identifier.uri https://hdl.handle.net/1813/7176 dc.description.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. en_US dc.format.extent 1207347 bytes dc.format.extent 10131373 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title Newtonian Graphs, Riemann Surfaces and Computation en_US dc.type technical report en_US
﻿