+\begin{equation}
+ {\Large \forall a_{i} \in C, i\in N; p(x)=\sum^{n}_{i=0} a_{i}.x^{i}}
+\end{equation}
+For our tests, a CPU Intel(R) Xeon(R) CPU E5620@2.40GHz and a GPU K40 (with 6 Go of ram) are used.
+%SIDER : Une meilleure présentation de l'architecture est à faire ici.
+For our test, a cluster of computing with 72 nodes, 1116 cores, 4 cards GPU tesla Kepler K40 are used,
+In order to evaluate both the M-GPU and Multi-GPU approaches, we performed a set of experiments on a single GPU and multiple GPUs using OpenMP or MPI by EA algorithm, for both sparse and full polynomials of different sizes.
+All experimental results obtained are made in double precision data whereas the convergence threshold of the EA method is set to $10^{-7}$.
+%Since we were more interested in the comparison of the
+%performance behaviors of Ehrlich-Aberth and Durand-Kerner methods on
+%CPUs versus on GPUs.
+The initialization values of the vector solution
+of the methods are given by Guggenheimer method~\cite{Gugg86} %Section~\ref{sec:vec_initialization}.
+
+\subsection{Evaluating the M-GPU (CUDA-OpenMP) approach}
+
+We report here the results of the set of experiments with the M-GPU approach for full and sparse polynomials of different degrees, and we compare it with a Single GPU execution.
+\subsubsection{Execution time of the EA method for solving sparse polynomials on multiple GPUs using the M-GPU approach}
+
+In this experiments we report the execution time of the EA algorithm, on single GPU and Multi-GPU with (2,3,4) GPUs, for different sparse polynomial degrees ranging from 100,000 to 1,400,000.
+
+\begin{figure}[htbp]
+\centering
+ \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_omp}
+\caption{Execution time in seconds of the Ehrlich-Aberth method for solving sparse polynomials on multiple GPUs using the M-GPU approach}
+\label{fig:01}
+\end{figure}
+
+This figure~\ref{fig:01} shows that the (CUDA-OpenMP) M-GPU approach reduces the execution time by a factor up to 100 w.r.t the single GPU approach and a by a factor of 1000 for polynomials exceeding degree 1,000,000. It shows the advantage to use the OpenMP parallel paradigm to gather the capabilities of several GPUs and solve polynomials of very high degrees.
+
+\subsubsection{Execution time in seconds of the Ehrlich-Aberth method for solving full polynomials on multiple GPUs using the M-GPU approach}
+
+The experiments shows the execution time of the EA algorithm, on a single GPU and on multiple GPUs using the CUDA OpenMP approach for full polynomials of degrees ranging from 100,000 to 1,400,000.
+
+\begin{figure}[htbp]
+\centering
+ \includegraphics[angle=-90,width=0.5\textwidth]{Full_omp}
+\caption{Execution time in seconds of the Ehrlich-Aberth method for solving full polynomials on multiple GPUs using the M-GPU appraoch}
+\label{fig:03}
+\end{figure}
+
+Results with full polynomials show very important savings in execution time. For a polynomial of degree 1,4 million, the CUDA-OpenMP approach with 4 GPUs solves it 4 times as fast as single GPU, thus achieving a quasi-linear speedup.
+
+\subsection{Evaluating the Multi-GPU (CUDA-MPI) approach}
+In this part we perform a set of experiments to compare the Multi-GPU (CUDA MPI) approach with a single GPU, for solving full and sparse polynomials of degrees ranging from 100,000 to 1,400,000.
+
+\subsubsection{Execution time of the Ehrlich-Aberth method for solving sparse polynomials on multiple GPUs using the Multi-GPU approach}
+
+\begin{figure}[htbp]
+\centering
+ \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_mpi}
+\caption{Execution time in seconds of the Ehrlich-Aberth method for solving sparse polynomials on multiple GPUs using the Multi-GPU approach}
+\label{fig:02}
+\end{figure}
+~\\
+Figure~\ref{fig:02} shows execution time of EA algorithm, for a single GPU, and multiple GPUs (2, 3, 4) on respectively 2, 3 and four MPI nodes. We can clearly see that the curve for a single GPU is above the other curves, which shows overtime in execution time compared to the Multi-GPU approach. We can see also that the CUDA-MPI approach reduces the execution time by a factor of 10 for polynomials of degree more than 1,000,000. For example, at degree 1,000,000, the execution time with a single GPU amounted to 10 thousand seconds, while with 4 GPUs, it is lowered to about just one thousand seconds which makes it for a tenfold speedup.
+%%SIDER : Je n'ai pas reformuler car je n'ai pas compris la phrase, merci de l'ecrire ici en fran\cais.
+\\cette figure montre 4 courbes de temps d'exécution pour l'algorithme EA, une courbe avec un seul GPU, 3 courbes pour multiple GPUs(2, 3, 4), on peut constaté clairement que la courbe à un seul GPU est au-dessus des autres courbes, vue sa consommation en temps d'exècution. On peut voir aussi qu'avec l'approche Multi-GPU (CUDA-MPI) reduit le temps d'exècution jusqu'à l'echelle 100 pour le polynômes qui dépasse 1,000,000 tandis que Single GPU est de l'echelle 1000.
+
+\subsubsection{Execution time of the Ehrlich-Aberth method for solving full polynomials on multiple GPUs using the Multi-GPU appraoch}
+
+\begin{figure}[htbp]
+\centering
+ \includegraphics[angle=-90,width=0.5\textwidth]{Full_mpi}
+\caption{Execution times in seconds of the Ehrlich-Aberth method for full polynomials on GPUs using the Multi-GPU}
+\label{fig:04}
+\end{figure}
+
+
+ Figure \ref{fig:04} shows execution time for a single GPU, and multiple GPUs (2, 3, 4) on respectively 2, 3 and four MPI nodes. With the CUDA-MPI approach, we notice that the three curves are distinct from each other, more we use GPUs more the execution time decreases. On the other hand the curve for a single GPU is well above the other curves.
+
+This is due to the use of MPI parallel paradigm that divides the problem computations and assigns portions to each GPU. But unlike the single GPU which carries all the computations on a single GPU, data communications are introduced, consequently engendering more execution time. But experiments show that execution time is still highly reduced.
+
+
+
+\subsection{Comparing the CUDA-OpenMP approach and the CUDA-MPI approach}
+
+In the previuos section we saw that both approches are very effective in reducing execution time for sparse as well as full polynomials. At this stage, the interesting question is which approach is better. In the fellowing, we present appropriate experiments comparing the two Multi-GPU approaches to answer the question.
+
+\subsubsection{Solving sparse polynomials}
+In this experiment three sparse polynomials of size 200K, 800K and 1,4M are investigated.
+\begin{figure}[htbp]
+\centering
+ \includegraphics[angle=-90,width=0.5\textwidth]{Sparse}
+\caption{Execution time for solving sparse polynomials of three distinct sizes on multiple GPUs using MPI and OpenMP approaches using Ehrlich-Aberth}
+\label{fig:05}
+\end{figure}
+In Figure~\ref{fig:05} there two curves for each polynomial size : one for the MPI-CUDA and another for the OpenMP. We can see that the results are similar between OpenMP and MPI for the polynomials size of 200K. For the size of 800K, the MPI version is a little slower than the OpenMP approach but for the 1,4 millions size, there is a slight advantage for the MPI version.
+
+\subsubsection{Solving full polynomials}
+\begin{figure}[htbp]
+\centering
+ \includegraphics[angle=-90,width=0.5\textwidth]{Full}
+\caption{Execution time for solving full polynomials of three distinct sizes on multiple GPUs using MPI and OpenMP approaches using Ehrlich-Aberth}
+\label{fig:06}
+\end{figure}
+In Figure~\ref{fig:06}, we can see that when it comes to full polynomials, both approaches are almost equivalent.
+
+\subsubsection{Solving sparse and full polynomials of the same size with CUDA-MPI}
+In this experiment we compare the execution time of the EA algorithm according to the number of GPUs for solving sparse and full polynomials on Multi-GPU using MPI. We chose three sparse and full polynomials of size 200K, 800K and 1,4M.
+\begin{figure}[htbp]
+\centering
+ \includegraphics[angle=-90,width=0.5\textwidth]{MPI}
+\caption{Execution time for solving sparse and full polynomials of three distinct sizes on multiple GPUs using MPI}
+\label{fig:07}
+\end{figure}
+in figure ~\ref{fig:07} we can see that CUDA-MPI can solve sparse and full polynomials of high degrees, the execution time with sparse polynomial are very low comparing to full polynomials. with sparse polynomials the number of monomial are reduce, consequently the number of operation are reduce than the execution time decrease.
+
+\subsubsection{Solving sparse and full polynomials of the same size with CUDA-OpenMP}
+
+\begin{figure}[htbp]
+\centering
+ \includegraphics[angle=-90,width=0.5\textwidth]{OMP}
+\caption{Execution time for solving sparse and full polynomials of three distinct sizes on multiple GPUs using OpenMP}
+\label{fig:08}
+\end{figure}
+
+Figure ~\ref{fig:08} shows the impact of sparsity on the effectiveness of the CUDA-OpenMP approach. We can see that the impact fellows the same pattern, a difference in execution time in favor of the sparse polynomials.
+%SIDER : il faut une explication ici. je ne vois pas de prime abords, qu'est-ce qui engendre cette différence, car quelques soient les coefficients nulls ou non nulls, c'est toutes les racines qui sont calculées qu'elles soient similaires ou non (degrés de multiplicité).
+\subsection{Scalability of the EA method on Multi-GPU to solve very high degree polynomials}
+These experiments report the execution time according to the degrees of polynomials ranging from 1,000,000 to 5,000,000 for both approaches with sparse and full polynomials.
+\begin{figure}[htbp]
+\centering
+ \includegraphics[angle=-90,width=0.5\textwidth]{big}
+ \caption{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials of high degree on 4 GPUs for sizes ranging from 1M to 5M}
+\label{fig:09}
+\end{figure}
+In figure ~\ref{fig:09} we can see that both approaches are scalable and can solve very high degree polynomials. With full polynomial both approaches give interestingly very similar results. For the sparse case however, there are a noticeable difference in favour of MPI when the degree is above 4M. Between 1M and 3M, the OMP approach is more effective and under 1M degree, OMP and MPI approaches are almost equivalent.
+
+%SIDER : il faut une explication sur les différences ici aussi.
+
+%for sparse and full polynomials
