\end{align}
%%\end{equation}
-Using the logarithm (eq. \ref{deflncomplex}) and the exponential (eq. \ref{defexpcomplex}) operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations
+Using the logarithm (eq.~\ref{deflncomplex}) and the exponential (eq.~\ref{defexpcomplex}) operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations
manipulate lower absolute values and the roots for large polynomial's degrees can be looked for successfully~\cite{Karimall98}.
Applying this solution for the Aberth method we obtain the
\subsubsection{A sequential Aberth algorithm}
-The main steps of Aberth method are shown in Algorithm.\ref{alg1-seq} :
+The main steps of Aberth method are shown in Algorithm.~\ref{alg1-seq} :
\begin{algorithm}[H]
\label{alg1-seq}
H(i,z^{k+1})=\frac{p(z^{(k)}_{i})}{p'(z^{(k)}_{i})-p(z^{(k)}_{i})(\sum^{i-1}_{j=1}\frac{1}{z^{(k)}_{i}-z^{(k+1)}_{j}}+\sum^{n}_{j=i+1}\frac{1}{z^{(k)}_{i}-z^{(k)}_{j}})}, i=1,...,n.
\end{equation}
-Using Equation.\ref{eq:Aberth-H-GS} for the update sub-step of $H(i,z^{k+1})$, we expect the Gauss-Seidel iteration to converge more quickly because, just as its ancestor (for solving linear systems of equations), it uses the most fresh computed roots $z^{k+1}_{i}$.
+Using Equation.~\ref{eq:Aberth-H-GS} for the update sub-step of $H(i,z^{k+1})$, we expect the Gauss-Seidel iteration to converge more quickly because, just as its ancestor (for solving linear systems of equations), it uses the most fresh computed roots $z^{k+1}_{i}$.
-The $4^{th}$ step of the algorithm checks the convergence condition using Equation.\ref{eq:Aberth-Conv-Cond}.
+The $4^{th}$ step of the algorithm checks the convergence condition using Equation.~\ref{eq:Aberth-Conv-Cond}.
Both steps 3 and 4 use 1 thread to compute all the $n$ roots on CPU, which is very harmful for performance in case of the large degree polynomials.
\paragraph{The execution time}
\begin{equation}
T_{iter}=n(T_{i}(n)+T_{j})+O(n).
\end{equation}
-Let $K$ be the number of iterations necessary to compute all the roots, so the total execution time $Total\_time$ can be given as:
+Let $K$ be the number of iterations necessary to compute all the roots, so the total execution time $T$ can be given as:
\begin{equation}
-Total\_time=\left[n\left(T_{i}(n)+T_{j}\right)+O(n)\right].K
+\label{eq:T-global}
+T=\left[n\left(T_{i}(n)+T_{j}\right)+O(n)\right].K
\end{equation}
The execution time increases with the increasing of the polynomial degree, which justifies to parallelise these steps in order to reduce the global execution time. In the following, we explain how we did parrallelize these steps on a GPU architecture using the CUDA platform.
-\subsubsection{Parallelize the steps on GPU }
-On the CPU Aberth algorithm both steps 3 and 4 contain the loop \verb=for=, it use one thread to execute all the instruction in the loop N times. Here we explain how the GPU architecture can compute this loop and reduce the execution time.
-The GPU architecture assign the execution of this loop to a groups of parallel threads organized as a grid of blocks each block contain a number of threads. All threads within a block are executed concurrently in parallel. The instruction are executed as a kernel.
+\subsubsection{A Parallel implementation on a GPU }
+On the CPU, both steps 3 and 4 contain the loop \verb=for= and a single thread executes all the instructions in the loop $n$ times. In this subsection, we explain how the GPU architecture can compute this loop and reduce the execution time.
+In the GPU, the schduler assigns the execution of this loop to a group of threads organised as a grid of blocks with block containing a number of threads. All threads within a block are executed concurrently in parallel. The instructions run on the GPU are grouped in special function called kernels. It's up to the programmer, to describe the execution context, that is the size of the Grid, the number of blocks and the number of threads per block upon the call of a given kernel, according to a special syntax defined by CUDA.
-Let nbr\_thread be the number of threads executed in parallel, so you can easily transform the (18)formula like this:
+Let N be the number of threads executed in parallel, Equation.~\ref{eq:T-global} becomes then :
\begin{equation}
-Total\_time_{exe}=\left[\frac{N}{nbr\_thread}\left(T_{i}(N)+T_{j}\right)+O(n)\right].Nbr\_iter.
+T=\left[\frac{n}{N}\left(T_{i}(n)+T_{j}\right)+O(n)\right].K.
\end{equation}
-In theory, the $Total\_time_{exe}$ on GPU is speed up nbr\_thread times as a $Total\_time_{exe}$ on CPU. We show more details in the experiment part.
+In theory, total execution time $T$ on GPU is speed up $N$ times as $T$ on CPU. We will see at what extent this is true in the experimental study hereafter.
~\\
~\\
-In CUDA platform, All the instruction of the loop \verb=for= are executed by the GPU as a kernel form. A kernel is a procedure written in CUDA and defined by a heading \verb=__global__=, which means that it is to be executed by the GPU. The following algorithm see the Aberth algorithm on GPU:
+In CUDA programming, all the instructions of the \verb=for= loop are executed by the GPU as a kernel. A kernel is a function written in CUDA and defined by the \verb=__global__= qualifier added before a usual ``C`` function, which instructs the compiler to generate appropriate code to pass it to the CUDA runtime in order to be executed on the GPU.
+
+Algorithm~\ref{alg2-cuda} shows a sketch of the Aberth algorithm usind CUDA.
\begin{algorithm}[H]
+\label{alg2-cuda}
%\LinesNumbered
-\caption{Algorithm to find root polynomial with Aberth method}
+\caption{CUDA Algorithm to find roots of polynomial with Aberth method}
\KwIn{$Z^{0}$(Initial root's vector),$\varepsilon$ (error
tolerance threshold),P(Polynomial to solve)}
\BlankLine
-Initialization of the parameter of the polynomial to solve\;
+Initialization of the coeffcients of the polynomial to solve\;
Initialization of the solution vector $Z^{0}$\;
-Allocate and fill the data in the global memory GPU\;
+Allocate and copy initial data to the GPU global memory\;
\While {$\Delta z_{max}\succ \epsilon$}{
Let $\Delta z_{max}=0$\;
\end{table}
+
+\begin{figure}[htbp]
+\centering
+ \includegraphics[width=0.8\textwidth]{figures/influence_nb_threads}
+\caption{Influence of the number of threads on the execution times of different polynomials (sparse and full)}
+\label{fig:01}
+\end{figure}
+
+
+
\paragraph{A comparative study between Aberth and Durand-kerner algorithm}
\begin{table}[htbp]
\centering
