%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%KWD: geometric progression
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Name{ Roots in geometric progression along a spiral }
\Ring{ \CC[x]}

\begin{Equations}
\prod_{j=1}^n(x+{a^j-1\over a-1}), |a|<<1, (n=20, a=i/1000, a=(3+4 i)/10)
\end{Equations}
Suppplied by D. A. Bini (Oct. 1996).
% II ORIGIN OF THE PROBLEM

\begin{Characteristics}
 \item The polynomial has roots along a spiral centered in $1/(a-1)$, where
       the distances of the $j$-th zero from the center of the spiral
       approach exponentially $0$.
 \item For $n=20$, $a=i/1000$ the condition number of the roots ranges from
       $10^{30}$ to $10^{138}$. The closest roots have about 60 common digits.
       In this way a working precision of 198 digits is needed for
       separating the
       closest roots. The numerators and the denominators of the coefficients
       have at most 132 digits.

 \item Large values of $n$, say $n=500,1000,2000$, constitute an
       interesting test for polynomial root-finders.
\end{Characteristics}


% IV THE KIND OF PROBLEM WE ARE SOLVING
\begin{Problem}
Newton-isolate all the roots.
\end{Problem}

% V LIST OF SOLUTIONS
\begin{Solution}
 Algorithm based on simultaneous iterations (Aberth's method)
with cluster analysis (see \cite{Bini97abrt}).

 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 $a=(3+4 i)/10$, $n=20$:
46 seconds.


\Signature
{Dario Andrea Bini, Dipartimento di Matematica, via Buonarroti 2,
 56127 Pisa, ITALY}                    % <- Name(s) and Adress(es)
{bini@dm.unipi.it}                   % <- email and/or www adress
{October 15, 1996}               % <- Date of the experimentation.
\end{Solution}


