Re: polroots algorithm

[Karim Belabas <karim@mpim-bonn.mpg.de>]

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