%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%KWD: n-roots
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Name{ N-th Roots }
\Ring{\CC[x], \RR[x]}

\begin{Equations}
x^n-a, \ \  (n=20,  a=1)
\end{Equations}

% II ORIGIN OF THE PROBLEM
Supplied by D. A. Bini (Oct. 1996).

\begin{Characteristics}
 \item Sparse polynomial.
 \item The polynomial has roots equidistributed along a circle, for $a=1$
        they are the $n$-th roots of the unity.
 \item Even though the roots come close together as $n$ grows, they are
numerically
       well conditioned. Their condition number is at most $2/n$.
 \item Interesting cases are given by large values of $n$, say,
$n=500,1000,10000$.
 \item Due to its specificity, the polynomial can be assigned as a
straight-line program.
\end{Characteristics}


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

% V LIST OF SOLUTIONS CONTAINING THE AUTHORS NAME, THE DATE,
\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 $n=20$, $a=1$: 0.1 seconds;
for $n=200$, $a=1$: 0.57 seconds;
for $n=500$, $a=1$: 3.4  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}



