From: Kahina Date: Thu, 29 Oct 2015 15:18:46 +0000 (+0100) Subject: Quelque modification de la partie theorique X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/kahina_paper1.git/commitdiff_plain/a0b86a3fc76a67a77f449747d62d31f27ddf0506 Quelque modification de la partie theorique --- diff --git a/figures/EA_DK.txt b/figures/EA_DK.txt index 187bb3a..6414285 100644 --- a/figures/EA_DK.txt +++ b/figures/EA_DK.txt @@ -7,11 +7,11 @@ 150000 28.67 17 156.63 33 200000 40 23 330.456 43 250000 93.76 20 518.342 47 -300000 138.94 21 912.078 50 -350000 159.65 18 1398.64 56 -400000 258.91 22 3112 20 +300000 138.94 21 313.697 21 +350000 159.65 18 28 +400000 258.91 22 580.649 20 450000 339.47 23 -500000 419.78 23 +500000 419.78 23 739.882 28 550000 415.94 19 600000 549.70 21 650000 612.12 20 diff --git a/paper.tex b/paper.tex index 9fee850..bcac7f4 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 @@ -510,13 +510,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}$.