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
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
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
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
\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}
\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
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}$.
