\usepackage[ruled,vlined]{algorithm2e}
%\usepackage[french,boxed,linesnumbered]{algorithm2e}
\usepackage{array,multirow,makecell}
+
+\newcommand{\RC}[2][inline]{%
+ \todo[color=blue!10,#1]{\sffamily\textbf{RC:} #2}\xspace}
+\newcommand{\KG}[2][inline]{%
+ \todo[color=green!10,#1]{\sffamily\textbf{KG:} #2}\xspace}
+\newcommand{\AS}[2][inline]{%
+ \todo[color=orange!10,#1]{\sffamily\textbf{AS:} #2}\xspace}
+
+
\setcellgapes{1pt}
\makegapedcells
\newcolumntype{R}[1]{>{\raggedleft\arraybackslash }b{#1}}
\newcolumntype{C}[1]{>{\centering\arraybackslash }b{#1}}
\modulolinenumbers[5]
+
+
\journal{Journal of \LaTeX\ Templates}
%%%%%%%%%%%%%%%%%%%%%%%
algorithm for the root finding problem for high degree polynomials on
GPU architectures. The main result of this
work is to be able to solve high degree polynomials (up
-to 1,000,000) very efficiently. We also compare the results with a
+to 1,000,000) efficiently. We also compare the results with a
sequential implementation and the Durand-Kerner method on full and
sparse polynomials.
\end{abstract}
\subsection{Comparison of the Durand-Kerner and the Ehrlich-Aberth methods}
In this part, we compare the Durand-Kerner and the Ehrlich-Aberth
-methods on GPU. We took into account the execution times, the number of iterations and the polynomials size for the both sparse and full polynomials.
+methods on GPU. We took into account the execution times, the number of iterations and the polynomials size for both sparse and full polynomials.
\begin{figure}[htbp]
\centering
Figure~\ref{fig:04} shows the execution times of both methods with
sparse polynomial degrees ranging from 1,000 to 1,000,000. We can see
that the Ehrlich-Aberth algorithm is faster than Durand-Kerner
-algorithm, with an average of 25 times faster. Then, when degrees of
-polynomial exceed 500,000 the execution times with DK are very long.
+algorithm, being on average 25 times faster. Then, when degrees of
+polynomials exceed 500,000 the execution times with DK are very long.
%with double precision not exceed $10^{-5}$.
\label{fig:05}
\end{figure}
-Figure~\ref{fig:05} show the evaluation of the number of iteration according
-to degree of polynomial from both EA and DK algorithms, we can see
-that the iteration number of DK is of order 100 while EA is of order
-10. Indeed the computing of the derivative of P (the polynomial to
-resolve) in the iterative function (Eq.~\ref{Eq:Hi}) executed by EA
-allows the algorithm to converge more quickly. In counterpart, the
-DK operator (Eq.~\ref{DK}) needs low operation, consequently low
-execution time per iteration, but it needs more iterations to converge.
+Figure~\ref{fig:05} shows the evaluation of the number of iterations according
+to the degree of polynomials for both EA and DK algorithms. We can see
+that the number of iterations of DK is of order 100 while EA is of order
+10. Indeed the computation of the derivative of P in the iterative function (Eq.~\ref{Eq:Hi}) executed by EA
+allows the algorithm to converge faster. On the contrary, the
+DK operator (Eq.~\ref{DK}) needs low operations, consequently low
+execution times per iteration, but it needs more iterations to converge.
+
+
\section{Conclusion and perspectives}
polynomials.
We have performed many experiments with the Ehrlich-Aberth method in
-GPU. These experiments highlight that this method is very efficient in
-GPU compared to all the other implementations. The improvement with
+GPU. These experiments highlight that this method is more efficient in
+GPU than all the other implementations. The improvement with
the exponential logarithm solution allows us to solve sparse and full
high degree polynomials up to 1,000,000 degree. Hence, it may be
-possible to consider to use polynomial root finding methods in other
+possible to consider using polynomial root finding methods in other
numerical applications on GPU.
In future works, we plan to investigate the possibility of using
-several multiple GPUs simultaneously, either with multi-GPU machine or
-with cluster of GPUs. It may also be interesting to study the
+several multiple GPUs simultaneously, either with a multi-GPU machine or
+with a cluster of GPUs. It may also be interesting to study the
implementation of other root finding polynomial methods on GPU.
