On Sep 4, 9:35 am, "John Voight" <[EMAIL PROTECTED]> wrote: > In my situation, I have the following absurdly easy case: I have a > real interval in which I know there is exactly one real root which I > need to know to maybe 6 or 10 digits of precision. The polynomials > are monic, have small integer coefficients (bounded in absolute value > by maybe 100 or so), and have small degree (<= 11). The problem is > that there are zillions of them--so I need this data very quickly! > > Any advice would be most appreciated.
OK; my root isolation code will not help you at all. (It's particularly efficient at finding real intervals containing exactly one root; but if you already have such an interval, other methods for refining the root will be faster.) I haven't looked much at techniques for refining real roots (it's not the part of the problem that interests me, and for my applications, it's not the bottleneck), so take what I say with a grain of salt. If your intervals are small enough that you get good convergence from Newton-Raphson, then I would guess that's probably your best bet (it's simple, and for only 10 digits of precision you don't need very many iterations). I believe there are asymptotically faster methods, but I don't know if they would be faster in practice for such a small problem. If you have larger intervals, you might want something more complicated like Brent's method (http://en.wikipedia.org/wiki/Brent %27s_method). (I only know about Brent's method from that Wikipedia article.) If you're still not satisfied with the speed (if the profiling from %prun indicates that root refinement is taking a lot of your time), my next suggestion would be to read through the Cython-generated C code and verify that all of the inner loops are using only C data types, rather than creating Python objects. Sorry I couldn't be more help. 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/ -~----------~----~----~----~------~----~------~--~---
