On Tuesday, December 16, 2014 12:14:09 PM UTC+1, Jeroen Demeyer wrote: > > Hello sage-devel, > > I am wondering if there is an algorithm implemented in Sage which can > isolate a complex root of a given polynomial? > > The typical use case is that I have a polynomial for which I know one > approximate root and I want to find a complex interval around that root > which contains no other roots. The point is that I need to do this for > just one root, not all roots of the given polynomial. > > The input polynomial has exact (ZZ or QQ) coefficients. >
The problem can be solved in two stages using interval arithmetic: (1) find a complex interval guaranteed to contain at least one root (2) prove that this interval contains at most one root A very elegant solution to (1) is given by corollary 6.4g in Henrici's Applied and computational complex analysis: if f has degree n, then the disk of radius n*|f(z)/f'(z)| centered at z is guaranteed to contain at least one root of f. If you compute all roots simultaneously, then this is all you need, because you can just check that you have n pairwise disjoint intervals each containing at least one root. Otherwise, a fairly simple solution for (2) is given by Sagraloff and Yap as part of their CEVAL algorithm (see "A simple but exact and efficient algorithm for complex root isolation"). Henrici also suggests a few different methods. I'm still looking for a good converse of Henrici's 6.4g for (2). In the real case, it is sufficient to test that f'(x) != 0 for all x in the interval (just a single polynomial evaluation using interval arithmetic). Is there an analogous test that holds on a complex disk? The CEVAL test should be good enough, so this is just a curiosity. Fredrik -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
