Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Computing the Newtonian Graph (Extended abstract)
Authors: Kozen, Dexter
Stefansson, Kjartan
Keywords: computer science
technical report
Issue Date: Oct-1993
Publisher: Cornell University
Abstract: A polynomial $f\in \complex[z]$ defines a vector field $N_f(z) = -f(z)/f'(z)$ on $\complex$. Certain degenerate curves of flow in $N_f$ give the edges of the Newtonian graph, as defined by \cite{Sma85}. These give a relation between the roots of $f$ and $f'$, much similar to the linear order, when $f$ has real roots only. We give a purely algebraic algorithm to compute the Newtonian graph and the basins of attraction in the Newtonian field. The resulting structure can be used to query whether two points in $\complex$ are within the same basin of attraction. This gives us an algebraic approach to root-finding using Newton's method. This method extends to rational functions and more generally to any functions on $\complex$ whose flow is algebraic over $\complex(e)$.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
93-1392.pdf1.47 MBAdobe PDFView/Open
93-1392.ps410.47 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us