%The issue of finding the roots of polynomials of very high degrees arises in many complex problems in various fields, such as algebra, biology, finance, physics or climatology [1]. In algebra for example, finding eigenvalues or eigenvectors of any real/complex matrix amounts to that of finding the roots of the so-called characteristic polynomial.
-Finding roots of polynomials of very high degrees arises in many complex problems in various domains such as algebra, biology or physics. A polynomial $p(x)$ in $\mathbb{C}$ in one variable $x$ is an algebraic expression in $x$ of the form
+Finding roots of polynomials of very high degrees arises in many complex problems in various domains such as algebra, biology or physics. A polynomial $p(x)$ in $\mathbb{C}$ in one variable $x$ is an algebraic expression in $x$ of the form:
\begin{equation}
p(x) = \displaystyle\sum^n_{i=0}{a_ix^i},a_0\neq 0.
\end{equation}
\forall i \in [1,n];\vert\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}\vert<\xi
\end{equation}
\subsection{Improving Ehrlich-Aberth method}
-......
+With high degree polynomial, the Ehrlich-Aberth method suffer from overflow because the limited number in the mantissa of floating points representations, which makes the computation of $p(z)$ wrong when z is large.
+
+Experimentally, it is very difficult to solve polynomials with Ehrlich-Aberth method and have roots which except the circle of unit, represented by the radius $r$ evaluated as:
+
+\begin{equation}
+\label{R.EL}
+R = exp(log(DBL\_MAX)/(2*n) );
+\end{equation}
+
+
+%\begin{equation}
+
+%R = \exp( \log(DBL\_MAX) / (2*n) )
+%\end{equation}
+ where \verb=DBL_MAX= stands for the maximum representable \verb=double= value.
+
+This problem was discussed earlier in~\cite{Karimall98} for the Durand-Kerner method. The authors
+propose to use the logarithm and the exponential of a complex in order to compute the power at a high exponent. Using the logarithm and the exponential operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations manipulate lower absolute values and the roots for large polynomial degrees can be looked for successfully~\cite{Karimall98}.
+
\subsection{Ehrlich-Aberth parallel implementation on CUDA}
We introduced three paradigms of parallel programming. Our objective consists in implementing a root finding polynomial algorithm on multiple GPUs. To this end, it is primordial to know how to manage CUDA contexts of different GPUs. A direct method for controlling the various GPUs is to use as many threads or processes as GPU devices. We can choose the GPU index based on the identifier of OpenMP thread or the rank of the MPI process. Both approaches will be investigated.
dependencies between threads or recursive computations must
be executed by only one CUDA or CPU thread (step 1 and step 2). Initially, we specify the organization of parallel threads, by specifying the dimension of the grid Dimgrid, the number of blocks per grid DimBlock and the number of threads per block.
-The code is organzed by what is named kernels, portions o code that are run on GPU devices. For step 3, there are two kernels, the
+The code is organized by what is named kernels, portions code that are run on GPU devices. For step 3, there are two kernels, the
first named \textit{save} is used to save vector $Z^{K-1}$ and the seconde one is named
\textit{update} and is used to update the $Z^{K}$ vector. For step 4, a kernel
tests the convergence of the method. In order to
\item Initialization of the solution vector $Z^{0}$\;
\item Allocate and copy initial data to the GPU global memory\;
\item k=0\;
-\While {$\Delta z_{max} > \epsilon$}{
-\item Let $\Delta z_{max}=0$\;
-\item $ kernel\_save(ZPrec,Z)$\;
-\item k=k+1\;
-\item $ kernel\_update(Z,P,Pu)$\;
+\item \While {$\Delta z_{max} > \epsilon$}{
+\item Let $\Delta z_{max}=0$\;
+\item $ kernel\_save(ZPrec,Z)$\;
+\item k=k+1\;
+\item $ kernel\_update(Z,P,Pu)$\;
\item $kernel\_testConverge(\Delta z_{max},Z,ZPrec)$\;
}
