Problem

Newton-isolate all the roots.

Solution

Algorithm based on simultaneous iterations (Aberth's method) with cluster analysis (see [1]).

Program in Fortran 90 based on the multiprecision package MPFUN, by D. Bailey.

Machine used: IBM Risc 6000.

Time for Newton-isolating all the roots: for n=20, 1.9 seconds; for n=50, 12.8 seconds; for n=100, 168 seconds.

Dario Andrea Bini, Dipartimento di Matematica, via Buonarroti 2, 56127 Pisa, ITALY bini@dm.unipi.it October 15, 1996

Solution

Here is an expr`erimentation, for exp100, with the MuPAD solver on a 300Mhz Pentium Pro, using Scho"nhage's algorithm.

##############################################################################

   *----*    MuPAD 1.3  ---  Multi Processing Algebra Data Tool
  /|   /|
 *----* |    Copyright (c) 1992-96 by B. Fuchssteiner, Automath
 | *--|-*    University of Paderborn.  All rights reserved.
 |/   |/
 *----*      Demo version, please register with                   
             MuPAD-distribution@uni-paderborn.de                  

>> PRETTY_PRINT:=FALSE:
>> p:=_plus(x^j/j!$j=0..100):
>> st:=time():               
>> float(hold(solve)(p,x));  
{- 2.80892445859493124588662021888231311195493331332270e1 + 7.675541135315\
92348425822994307916362158204847528000*I, - 2.8883690449261975526232768941\
3843882159036939390150e1 + 6.999308702824276349664627686202542641448902078\
21790e-1*I, - 2.87251625714633297310976039603038162121629853416640e1 + 3.4\
...
- 7.23021513023611497915605238987551876509548854513060 \
- 3.50147028680914245145268315608857836329159616313970e1*I, 9.831248714635\
74154639148891755968040707707617049860 - 4.1120160903587641756371559928203\
1756155858886372850e1*I}

>> time()-st;
1001000

See here the complete solution.

Paul Zimmerman, POLKA, INRIA Lorraine, Technopole de Nancy-Brabois, 615 rue du Jardin Botanique, BP 101, F-54600 Villers-les-Nancy Paul.Zimmermann@loria.fr February 9 1998