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

\begin{Equations}
(x^{n-k}+(a x+1)^m)(ax+1)^k, \ \ n>>m>1, \ n>>k>1,\ |a|>1, \ (n=20, m=3,
k=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 a cluster of $m$ very close roots around $-1/a$
       where $-1/a$ is also a multiple root of multiplicity $k$.

 \item Difficult situations can be obtained by tuning $n,m,k$ and $|a|$, say
$n=500$,
$m=10$, $k=2$, $a=10000$.
\end{Characteristics}


% IV THE KIND OF PROBLEM WE ARE SOLVING
\begin{Problem}
Newton-isolate all the roots up to within a relative error $10^{-100}$ for
nonisolated roots.

Newton-isolate all the root with automatic detection of multiplicity.

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=k=3$, $a=100i$, time needed for Newton-isolating all
 the roots up to within a relative error $10^{-100}$ for nonisolated roots:
 3.8 seconds;  with automatic detection of multiplicity: 7 seconds;
time for isolating the roots of modulus greater
 than 1: 0.88 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}


