Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Computing the Newtonian Graph (Extended abstract)

Computing the Newtonian Graph (Extended abstract)

File(s)
93-1392.ps (410.47 KB)
93-1392.pdf (1.44 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6170
Collections
Computer Science Technical Reports
Author
Kozen, Dexter
Stefansson, Kjartan
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)$.

Date Issued
1993-10
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1392
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance