maj de la partie 5 Implementation of the EA method on GPU

[kahina_paper1.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 4d08b492717f54fae0791058fe16c7e516644786..93e111a25b99fa7ed144d0eda0446aaa3d4ae8f9 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -9,6 +9,15 @@
 \usepackage[ruled,vlined]{algorithm2e}
 %\usepackage[french,boxed,linesnumbered]{algorithm2e}
 \usepackage{array,multirow,makecell}
 \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}}
 \setcellgapes{1pt}
 \makegapedcells
 \newcolumntype{R}[1]{>{\raggedleft\arraybackslash }b{#1}}


@@ -16,6 +25,8 @@
 \newcolumntype{C}[1]{>{\centering\arraybackslash }b{#1}}
 \modulolinenumbers[5]
 
 \newcolumntype{C}[1]{>{\centering\arraybackslash }b{#1}}
 \modulolinenumbers[5]
 

+
+

 \journal{Journal of \LaTeX\ Templates}
 
 %%%%%%%%%%%%%%%%%%%%%%%
 \journal{Journal of \LaTeX\ Templates}
 
 %%%%%%%%%%%%%%%%%%%%%%%


@@ -88,7 +99,7 @@ the results of a parallel implementation of the Ehrlich-Aberth
 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
 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}
 sequential implementation and the Durand-Kerner method on full and
 sparse polynomials.
 \end{abstract}


@@ -810,7 +821,7 @@ high degree polynomials.
 \subsection{Comparison of the Durand-Kerner and the Ehrlich-Aberth methods}
 
 In this part, we  compare the Durand-Kerner and the Ehrlich-Aberth
 \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
 
 \begin{figure}[htbp]
 \centering


@@ -822,8 +833,8 @@ methods on GPU. We took into account the execution times, the number of iteratio
 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
 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}$.
 
 
 %with double precision not exceed $10^{-5}$.
 


@@ -835,14 +846,15 @@ polynomial exceed 500,000 the execution times with DK are very long.
 \label{fig:05}
 \end{figure}
 
 \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}
 
 
  \section{Conclusion and perspectives}


@@ -855,17 +867,17 @@ applied to the iterative function allows to solve high degree
 polynomials.
 
 We have performed many experiments with the Ehrlich-Aberth method in
 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
 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
 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.
 
 
 implementation of other root finding polynomial methods on GPU.