COMPUTING THE NEWTONIAN GRAPH

In his study of Newton's root approximation method, Smale (1985) defin ed the Newtonian graph of a complex univariate polynomial f. The verti ces of this graph are the roots of f and f' and the edges are the dege nerate curves of flow of the Newtonian vector field N-f(z) = -f(z)/f'( z). The embedded edges of this graph form the boundaries of root basin s in Newton's root approximation method. The graph defines a treelike relation on the roots of f and f', similar to the linear order when f has only real roots. We give an efficient algebraic algorithm based on cell decomposition to compute the Newtonian graph. The resulting stru cture can be used to query whether two points in C are in the same bas in. This suggests a modified version of Neaten's method in which one c an test whether a step has crossed a basin boundary. We show that this modified version does not necessarily converge to a root. Stefansson (1995) has recently extended this algorithm to handle rational and alg ebraic functions without a significant increase in complexity. He has shown that the Newtonian graph tesselates the associated Riemann surfa ce and can be used in conjunction with Euler's formula to give an NC a lgorithm to calculate the genus of an algebraic curve. (C) 1997 Academ ic Press Limited.