X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/kahina_paper1.git/blobdiff_plain/6d04681fa87aadf0e6303a76c9c319fb79948d10..705f945860e432e730f66cdf91d7599b1e3cd3aa:/paper.tex diff --git a/paper.tex b/paper.tex index 9fee850..bcf399a 100644 --- 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} - 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 @@ -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} - 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 @@ -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. -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 @@ -206,7 +207,7 @@ hardware resources provided by GPU in order to offer a stronger 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 @@ -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 -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} -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} @@ -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 -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} -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} - +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 @@ -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} -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} @@ -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} -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} -With 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. +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}$. @@ -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} -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.