la section 3

[kahina_paper1.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 9fee850fbfa1c35aff39f3254619f1b4267ae742..bcf399a3b5c7b8109b9046412ec75e0961cf30c0 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -147,7 +147,7 @@ approximation of all the roots, starting with the Durand-Kerner (DK)
 method:
 %%\begin{center}
 \begin{equation}
 method:
 %%\begin{center}
 \begin{equation}

- z_i^{k+1}=z_{i}^k-\frac{P(z_i^k)}{\prod_{i\neq j}(z_i^k-z_j^k)}
+ z_i^{k+1}=z_{i}^{k}-\frac{P(z_i^{k})}{\prod_{i\neq j}(z_i^{k}-z_j^{k})},   i = 1, . . . , n,

 \end{equation}
 %%\end{center}
 where $z_i^k$ is the $i^{th}$ root of the polynomial $P$ at the
 \end{equation}
 %%\end{center}
 where $z_i^k$ is the $i^{th}$ root of the polynomial $P$ at the


@@ -164,7 +164,8 @@ in the following form by Ehrlich~\cite{Ehrlich67} and
 Aberth~\cite{Aberth73} uses a different iteration formula given as fellows :
 %%\begin{center}
 \begin{equation}
 Aberth~\cite{Aberth73} uses a different iteration formula given as fellows :
 %%\begin{center}
 \begin{equation}

- z_i^{k+1}=z_i^k-\frac{1}{{\frac {P'(z_i^k)} {P(z_i^k)}}-{\sum_{i\neq j}\frac{1}{(z_i^k-z_j^k)}}}.
+\label{Eq:EA}
+ z_i^{k+1}=z_i^{k}-\frac{1}{{\frac {P'(z_i^{k})} {P(z_i^{k})}}-{\sum_{i\neq j}\frac{1}{(z_i^{k}-z_j^{k})}}}, i = 1, . . . , n,

 \end{equation}
 %%\end{center}
 where $P'(z)$ is the polynomial derivative of $P$ evaluated in the
 \end{equation}
 %%\end{center}
 where $P'(z)$ is the polynomial derivative of $P$ evaluated in the


@@ -192,7 +193,7 @@ Freeman and Bane~\cite{Freemanall90}  considered asynchronous
 algorithms, in which each processor continues to update its
 approximations even though the latest values of other $z_i((k))$
 have not been received from the other processors, in contrast with synchronous algorithms where it would wait those values before making a new iteration.
 algorithms, in which each processor continues to update its
 approximations even though the latest values of other $z_i((k))$
 have not been received from the other processors, in contrast with synchronous algorithms where it would wait those values before making a new iteration.

-Couturier et al. ~\cite{Raphaelall01} proposed two methods of parallelisation for
+Couturier and al~\cite{Raphaelall01} proposed two methods of parallelisation for

 a shared memory architecture and for distributed memory one. They were able to
 compute the roots of polynomials of degree 10000 in 430 seconds with only 8
 personal computers and 2 communications per iteration. Comparing to the sequential implementation
 a shared memory architecture and for distributed memory one. They were able to
 compute the roots of polynomials of degree 10000 in 430 seconds with only 8
 personal computers and 2 communications per iteration. Comparing to the sequential implementation


@@ -206,7 +207,7 @@ hardware resources provided by GPU in order to offer a stronger
 computing ability to the massive data computing.
 
 
 computing ability to the massive data computing.
 
 

-Ghidouche et al. ~\cite{Kahinall14} proposed an implementation of the
+Ghidouche and al~\cite{Kahinall14} proposed an implementation of the

 Durand-Kerner method on GPU. Their main
 result showed that a parallel CUDA implementation is 10 times as fast as
 the sequential implementation on a single CPU for high degree
 Durand-Kerner method on GPU. Their main
 result showed that a parallel CUDA implementation is 10 times as fast as
 the sequential implementation on a single CPU for high degree


@@ -220,35 +221,33 @@ In Section \ref{sec5} we propose a parallel implementation of the Ehrlich-Aberth
 \section{The Sequential Aberth method}
 \label{sec1}
 A cubically convergent iteration method for finding zeros of
 \section{The Sequential Aberth method}
 \label{sec1}
 A cubically convergent iteration method for finding zeros of

-polynomials was proposed by O.Aberth~\cite{Aberth73}. The Aberth
-method is a purely algebraic derivation. To illustrate the
-derivation, we let $w_{i}(z)$ be the product of linear factors 
+polynomials was proposed by O. Aberth~\cite{Aberth73}. In the fellowing we present the main stages of the running of the Aberth method.
+%The Aberth method is a purely algebraic derivation. 
+%To illustrate the derivation, we let $w_{i}(z)$ be the product of linear factors 

 
 

-\begin{equation}
-w_{i}(z)=\prod_{j=1,j \neq i}^{n} (z-x_{j})
-\end{equation}
+%\begin{equation}
+%w_{i}(z)=\prod_{j=1,j \neq i}^{n} (z-x_{j})
+%\end{equation}

 
 

-And let a rational function $R_{i}(z)$ be the correction term of the
-Weistrass method~\cite{Weierstrass03}
+%And let a rational function $R_{i}(z)$ be the correction term of the
+%Weistrass method~\cite{Weierstrass03}

 
 

-\begin{equation}
-R_{i}(z)=\frac{p(z)}{w_{i}(z)} , i=1,2,...,n.
-\end{equation}
+%\begin{equation}
+%R_{i}(z)=\frac{p(z)}{w_{i}(z)} , i=1,2,...,n.
+%\end{equation}

 
 

-Differentiating the rational function $R_{i}(z)$ and applying the
-Newton method, we have:
+%Differentiating the rational function $R_{i}(z)$ and applying the
+%Newton method, we have:

 
 

-\begin{equation}
-\frac{R_{i}(z)}{R_{i}^{'}(z)}= \frac{p(z)}{p^{'}(z)-p(z)\frac{w_{i}(z)}{w_{i}^{'}(z)}}= \frac{p(z)}{p^{'}(z)-p(z) \sum _{j=1,j \neq i}^{n}\frac{1}{z-x_{j}}}, i=1,2,...,n
-\end{equation}
-where R_{i}^{'}(z)is the rational function derivative of F evaluated in the point z 
-Substituting $x_{j}$ for $z_{j}$ we obtain the Aberth iteration method.
+%\begin{equation}
+%\frac{R_{i}(z)}{R_{i}^{'}(z)}= \frac{p(z)}{p^{'}(z)-p(z)\frac{w_{i}(z)}{w_{i}^{'}(z)}}= \frac{p(z)}{p^{'}(z)-p(z) \sum _{j=1,j \neq i}^{n}\frac{1}{z-x_{j}}}, i=1,2,...,n
+%\end{equation}
+%where R_{i}^{'}(z)is the rational function derivative of F evaluated in the point z 
+%Substituting $x_{j}$ for $z_{j}$ we obtain the Aberth iteration method.% 

 
 

-In the fellowing we present the main stages of the running of the Aberth method.

 
 \subsection{Polynomials Initialization}
 
 \subsection{Polynomials Initialization}

-The initialization of a polynomial p(z) is done by setting each of the $n$ complex coefficients $a_{i}$
-:
+The initialization of a polynomial p(z) is done by setting each of the $n$ complex coefficients $a_{i}$:

 
 \begin{equation}
 \label{eq:SimplePolynome}
 
 \begin{equation}
 \label{eq:SimplePolynome}


@@ -282,14 +281,15 @@ v_{i}=\frac{|\frac{a_{n}}{a_{i}}|^{\frac{1}{n-i}}}{2}.
 
 \subsection{Iterative Function $H_{i}(z^{k})$}
 The operator used by the Aberth method is corresponding to the
 
 \subsection{Iterative Function $H_{i}(z^{k})$}
 The operator used by the Aberth method is corresponding to the

-following equation which will enable the convergence towards
+following equation~\ref{Eq:EA} which will enable the convergence towards

 polynomial solutions, provided all the roots are distinct.
 
 \begin{equation}
 polynomial solutions, provided all the roots are distinct.
 
 \begin{equation}

-H_{i}(z^{k+1})=z_{i}^{k}-\frac{1}{\frac{p^{'}(z_{i}^{k})}{p(z_{i}^{k})}-\sum_{j=1,j\neq
-i}^{j=n}{\frac{1}{z_{i}^{k}-z_{j}^{k}}}}
+\label{Eq:Hi}
+H_{i}(z^{k+1})=z_{i}^{k}-\frac{\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}}
+{1-\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}\sum_{j=1,j\neq i}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}}}, i=0,. . . .,n

 \end{equation}
 \end{equation}

-
+we notice that the function iterative $H_{i}$ in Eq.~\ref{Eq:Hi} it the same those presented in Eq.~\ref{Eq:EA}, but we prefer used the last one seen the advantage of its use to improve the Aberth method. More detail in the section ~\ref{sec2}.    

 \subsection{Convergence Condition}
 The convergence condition determines the termination of the algorithm. It consists in stopping from running
 the iterative function $H_{i}(z)$ when the roots are sufficiently stable. We consider that the method
 \subsection{Convergence Condition}
 The convergence condition determines the termination of the algorithm. It consists in stopping from running
 the iterative function $H_{i}(z)$ when the roots are sufficiently stable. We consider that the method


@@ -349,12 +349,16 @@ Q(z^{k}_{i})=\exp\left( \ln (p(z^{k}_{i}))-\ln(p'(z^{k}^{i}))+\ln \left(
 \sum_{k\neq j}^{n}\frac{1}{z^{k}_{i}-z^{k}_{j}}\right)\right).
 \end{equation}
 
 \sum_{k\neq j}^{n}\frac{1}{z^{k}_{i}-z^{k}_{j}}\right)\right).
 \end{equation}
 

-This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated as:
-\begin{equation}
-\label{R}
-R = \exp( \log(DBL\_MAX) / (2*n) )
-\end{equation}
- where $DBL\_MAX$ stands for the maximum representable double value.
+This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated in C language as:
+\begin{verbatim}
+R = exp(log(DBL_MAX)/(2*n) );
+\end{verbatim} 
+
+%\begin{equation}
+
+%R = \exp( \log(DBL\_MAX) / (2*n) )
+%\end{equation}
+ where \verb=DBL_MAX= stands for the maximum representable \verb=double= value.

 
 \section{The implementation of simultaneous methods in a parallel computer}
 \label{secStateofArt}   
 
 \section{The implementation of simultaneous methods in a parallel computer}
 \label{secStateofArt}   


@@ -510,13 +514,13 @@ In this sequential algorithm, one CPU thread  executes all the steps. Let us loo
 There exists two ways to execute the iterative function that we call a Jacobi one and a Gauss-Seidel one. With the Jacobi iteration, at iteration $k+1$ we need all the previous values $z^{(k)}_{i}$ to compute the new values $z^{(k+1)}_{i}$, that is :
 
 \begin{equation}
 There exists two ways to execute the iterative function that we call a Jacobi one and a Gauss-Seidel one. With the Jacobi iteration, at iteration $k+1$ we need all the previous values $z^{(k)}_{i}$ to compute the new values $z^{(k+1)}_{i}$, that is :
 
 \begin{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.
+z^{k+1}_{i}=\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}
 
 \end{equation}
 

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

 \begin{equation}
 \label{eq:Aberth-H-GS}
 \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.
+z^{k+1}_{i}=\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}
 %%Here a finiched my revision %%
 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}$.
 \end{equation}
 %%Here a finiched my revision %%
 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}$.


@@ -539,7 +543,7 @@ Let $K$ be the number of iterations necessary to compute all the roots, so the t
 \label{eq:T-global}
 T=\left[n\left(T_{i}(n)+T_{j}\right)+O(n)\right].K
 \end{equation}
 \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.
+The execution time increases with the increasing of the polynomial degree, which justifies to parallelize these steps  in order to reduce the global execution time. In the following,  we explain how we did parallelize these steps on a GPU architecture using the CUDA platform.

 
 \subsubsection{A Parallel implementation with CUDA }
 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.
 
 \subsubsection{A Parallel implementation with CUDA }
 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.