MAJ The comparative study

[kahina_paper1.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 02f98de83b7777e248bb3e8e5abe2441e3e5cbd9..35896aeff5ed485d271336c31dfbbf0bc59ef595 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -54,7 +54,7 @@
 
 \begin{frontmatter}
 
 
 \begin{frontmatter}
 

-\title{Parallel polynomial root finding  using GPU}
+\title{Rapid solution of very high degree polynomials root finding using GPU}

 
 %% Group authors per affiliation:
 \author{Elsevier\fnref{myfootnote}}
 
 %% Group authors per affiliation:
 \author{Elsevier\fnref{myfootnote}}


@@ -79,14 +79,12 @@
 \address[mysecondaryaddress]{FEMTO-ST Institute, University of Franche-Compté }
 
 \begin{abstract}
 \address[mysecondaryaddress]{FEMTO-ST Institute, University of Franche-Compté }
 
 \begin{abstract}

-in this article we present a parallel implementation
-of the Aberth algorithm for the problem root finding for
-high degree polynomials on GPU architecture (Graphics
-Processing Unit).
+Polynomials are mathematical algebraic structures that play a great role in science and engineering. But the process of solving them  for high and large degrees is computationally demanding and still not solved. In this paper, we present the results of a parallel implementation of the Ehrlish-Aberth algorithm for the problem root finding for
+high degree polynomials on GPU architectures (Graphics Processing Unit). The main result of this work is to be able to solve high and very large degree polynomials (up to 100000) very efficiently. We also compare the results with a sequential implementation and the Durand-Kerner method on full and sparse polynomials.

 \end{abstract}
 
 \begin{keyword}
 \end{abstract}
 
 \begin{keyword}

-root finding of polynomials, high degree, iterative methods, Durant-Kerner, GPU, CUDA, CPU , Parallelization
+root finding of polynomials, high degree, iterative methods, Ehrlish-Aberth, Durant-Kerner, GPU, CUDA, CPU , Parallelization

 \end{keyword}
 
 \end{frontmatter}
 \end{keyword}
 
 \end{frontmatter}


@@ -94,14 +92,19 @@ root finding of polynomials, high degree, iterative methods, Durant-Kerner, GPU,
 \linenumbers
 
 \section{The problem of finding roots of a polynomial}
 \linenumbers
 
 \section{The problem of finding roots of a polynomial}

-Polynomials are algebraic structures used in mathematics that capture physical phenomenons and that express the outcome in the form of a function of some unknown variable. Formally speaking,  a polynomial $p(x)$ of degree \textit{n} having $n$ coefficients in the complex plane \textit{C} and zeros $\alpha_{i},\textit{i=1,...,n}$ 
+Polynomials are mathematical algebraic structures used in science and engineering to capture physical phenomenons and to express any outcome in the form of a function of some unknown variables. Formally speaking,  a polynomial $p(x)$ of degree \textit{n} having $n$ coefficients in the complex plane \textit{C} is :

 %%\begin{center}
 \begin{equation}
 %%\begin{center}
 \begin{equation}

-     {\Large p(x)=\sum_{i=0}^{n}{a_{i}x^{i}}=a_{n}\prod_{i=1}^{n}(x-\alpha_{i}), a_{0} a_{n}\neq 0}.
+     {\Large p(x)=\sum_{i=0}^{n}{a_{i}x^{i}}}.

 \end{equation}
 %%\end{center}
 
 \end{equation}
 %%\end{center}
 

-The root finding problem consists in finding the values of all the $n$ values of the variable $x$ for which \textit{p(x)} is nullified. Such values are called zeroes of $p$. The problem of finding a root is equivalent to that of solving a fixed-point problem. To see this, consider the fixed-point problem of finding the $n$-dimensional
+The root finding problem consists in finding the values of all the $n$ values of the variable $x$ for which \textit{p(x)} is nullified. Such values are called zeroes of $p$. If zeros are $\alpha_{i},\textit{i=1,...,n}$ the $p(x)$ can be written as :
+\begin{equation}
+     {\Large p(x)=a_{n}\prod_{i=1}^{n}(x-\alpha_{i}), a_{0} a_{n}\neq 0}.
+\end{equation}
+
+The problem of finding a root is equivalent to that of solving a fixed-point problem. To see this, consider the fixed-point problem of finding the $n$-dimensional

 vector $x$ such that
 \begin{center}
 $x=g(x)$
 vector $x$ such that
 \begin{center}
 $x=g(x)$


@@ -331,7 +334,6 @@ Q(z_{k})=\exp\left( \ln (p(z_{k}))-\ln(p(z_{k}^{'}))+\ln \left(
 \end{equation}
 
 This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated as:
 \end{equation}
 
 This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated as:

-

 $$R = \exp( \log(DBL\_MAX) / (2*n) )$$ where $DBL\_MAX$ stands for the maximum representable double value.
 
 \section{The implementation of simultaneous methods in a parallel computer}
 $$R = \exp( \log(DBL\_MAX) / (2*n) )$$ where $DBL\_MAX$ stands for the maximum representable double value.
 
 \section{The implementation of simultaneous methods in a parallel computer}


@@ -490,7 +492,7 @@ There exists two ways to execute the iterative function that we call a Jacobi on
 H(i,z^{k+1})=\frac{p(z^{(k)}_{i})}{p'(z^{(k)}_{i})-p(z^{(k)}_{i})\sum^{n}_{j=1 j\neq i}\frac{1}{z^{(k)}_{i}-z^{(k)}_{j}}}, i=1,...,n.
 \end{equation}
 
 H(i,z^{k+1})=\frac{p(z^{(k)}_{i})}{p'(z^{(k)}_{i})-p(z^{(k)}_{i})\sum^{n}_{j=1 j\neq i}\frac{1}{z^{(k)}_{i}-z^{(k)}_{j}}}, i=1,...,n.
 \end{equation}
 

-With the the Gauss-seidel iteration, we have:
+With the Gauss-seidel iteration, we have:

 \begin{equation}
 \label{eq:Aberth-H-GS}
 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.
 \begin{equation}
 \label{eq:Aberth-H-GS}
 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.


@@ -619,7 +621,11 @@ E5620@2.40GHz and a GPU K40 (with 6 Go of ram).
 
 
 \subsection{Comparative study}
 
 
 \subsection{Comparative study}

-We initially carried out the convergence of Aberth algorithm with various sizes of polynomial, in second we evaluate the influence of the size of the threads per block....
+In this section, we discuss the performance Ehrlish-Aberth method  of root finding polynomials implemented on CPUs and on GPUs.
+
+We performed a set of experiments on the sequential and the parallel algorithms, for both sparse and full polynomials and different sizes. We took into account the execution time,the  polynomial size and the number of threads per block performed by sum or each experiment on CPUs and on GPUs.
+
+All experimental results obtained from the simulations are made in double precision data, for a convergence tolerance of the methods set to $10^{-7}$. Since we were more interested in the comparison of the performance behaviors of Ehrlish-Aberth and Durand-Kerner methods on CPUs versus on GPUs.

 
 \subsubsection{Aberth algorithm on CPU and GPU}
 
 
 \subsubsection{Aberth algorithm on CPU and GPU}