Karim Belabas on Sun, 22 Mar 1998 01:02:22 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polroots algorithm |
Genaldo L Nunes writes: > I am new to this list but have been using PARI-GP for a long time now. > Two years ago packages like MAPLE or MATHEMATICA was very slow in > finding roots of polynomials compared with pari-gp. The new version of > those packages seems faster now (they still have severe limitations). I > want to help improve pari performance since it is the one that I use. > I will look at the sources for the modified Newton method... The root finding routines in PARI (since version 1.900) are due to Xavier Gourdon and use an improved version of Shoenhage's algorithm. I modified them last year to integrate them better in the system, and two "bugs" were found since the first alpha release: one which caused the roots to be output in a different order on different machines (due to greater internal precision of register variables), and another one (fixed by Paul Zimmermann) which produced a floating point exception in exceedingly rare cases. Nobody is working on them at the moment and I consider them stable now (I might have overdone the garbage collecting simplification though, I'll have to recheck that on _huge_ examples, but that doesn't have high priority). Barring bugs, those routines return roots with guaranteed accuracy (up to degree ~ 1000). The main goal is not speed but robustness (contrary to both Maple and Mathematica which, to my knowledge, use fast heuristic algorithms and don't guarantee the result), although PARI still seems to be doing much better in practice. Xavier has conducted a detailed benchmark against Maple fsolve function in Chapter II.7 of his thesis. If you intend to work on this, I would advise to contact him first. In case you don't already have it, you can find Xavier's thesis online (in French) at: http://pauillac.inria.fr/algo/gourdon/thesis.html Karim. -- Karim Belabas e-mail: Max-Planck-Institut fuer Mathematik karim@mpim-bonn.mpg.de Gottfried-Claren-Str. 26 tel: 53225 Bonn (Germany) (00 49 228) 402-245