%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%KWD: Mignotte
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Name{ Mignotte-like Polynomial 1 }
\Ring{\CC[x], \RR[x]}

\begin{Equations}
    x^n+(a x+1)^m, \ \ n>>m>1, \ |a|>1,\  \ (n=20, m=3, a=100 i)
\end{Equations}

% II ORIGIN OF THE PROBLEM
The polynomial is a modification of Mignotte's polynomial $x^n+(a x+1)^2$
having two close roots whose distance is close to the Mahler bound.
Supplied by D. A. Bini (Oct. 1996).

\begin{Characteristics}
 \item The polynomial has $m$ very close roots around $-1/a$.
 \item For $n=20,m=3,a=100i$, there are 3 roots close to $-1/100 i$,
       matching in the first 13 digits. Their condition numbers are greater
       than $10^{25}$ so that at least 38 digits of working precision are needed
       for isolating the roots. The remaining roots are well conditioned and
       15 digits of working precision are sufficient to isolate them.
 \item Difficult situations can be obtained by tuning $n,m$ and $|a|$.
 \item Interesting situations are: the case of
     large degree and small cluster, i.e., $n=100,500$, $m=3$, $a=100 i$;
     the case of large degree and large cluster, i.e., $n=100,500$, $m=31$,
$a=1000$.
\end{Characteristics}


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

Newton-isolate all the roots of modulus greater than 1.

Count the number of roots of modulus greater than 1.
\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.

For $n=20,$ $m=3$, $a=100i$, time needed for isolating all
 the roots: 1.0 seconds;  time for isolating the roots of modulus greater
than 1: 0.4 seconds.

For $n=100,$ $m=3$, $a=100i$, time needed for isolating all
 the roots: 5.5 seconds;  time for isolating the roots of modulus greater
than 1: 0.6 seconds.

For $n=500,$ $m=3$, $a=100i$, time needed for isolating all
 the roots: 106 seconds;  time for isolating the roots of modulus greater
than 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}

