Show simple item record

dc.contributor.authorStefansson, Kjartanen_US
dc.date.accessioned2007-04-23T18:02:39Z
dc.date.available2007-04-23T18:02:39Z
dc.date.issued1995-05en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR95-1519en_US
dc.identifier.urihttps://hdl.handle.net/1813/7176
dc.description.abstractIn 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.extent1207347 bytes
dc.format.extent10131373 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleNewtonian Graphs, Riemann Surfaces and Computationen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics