On Sep 25, 9:28 am, "John Cremona" <[EMAIL PROTECTED]> wrote: > I thought this had been solved some time ago, and was implemented in > pari. Or is that only for real roots of real polynomials? > > John > > On 9/25/07, cwitty <[EMAIL PROTECTED]> wrote: > > The biggest obstacle to handling Qbar directly is that I haven't found > > a good way of isolating the roots of a complex polynomial (that is, > > finding the roots with a GUARANTEED error bound) and then refining a > > root to arbitrary precision.
Maybe so, but the documentation doesn't give enough detail for me to be confident. The documentation for Pari's polroots function says, "... it is guaranteed to converge and to give the roots to the required accuracy." But I don't know what that means. Am I supposed to trust every bit of the returned value (that is, the error is at most a half-ULP)? I'm fairly sure I could construct examples where determining a 100-bit result to within a half-ULP would require intermediate values that were a million bits. Does Pari go ahead and use the million-bit numbers here, or does it allow errors more than a half-ULP? If it allows errors more than a half-ULP, how large are the errors it does allow? Worse, I need to work with polynomials with inexact (interval) coefficients, and polynomial root-finding is inherently unstable (small changes in the coefficients can make large changes in the locations of the roots); even if Pari gives exactly-correct (within a half-ULP) answers for the polynomials you give it, how much do you increase the size of the interval outputs to account for the uncertainty in the inputs? All of this is to support a constructor that takes a polynomial with Qbar coefficients, and a complex interval (a rectangle in the complex plane) enclosing exactly one root, and return an element of Qbar. Instead, there could be a constructor that takes a polynomial with Qbar coefficients, and a complex interval enclosing exactly one root tightly enough that it can be arbitrarily refined using Newton- Raphson; and then it would be the responsibility of the caller to find such a complex interval. But how would the caller do that? Carl --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
