\documentclass[11pt,a4paper]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\author{ghidouche}
\title{Paper1_kahina}
\begin{document}
\section{Root finding problem}
we consider a polynomial of degree \textit{n} having coefficients
in the complex \textit{C} and zeros $\alpha
_{i},\textit{i=1,...,n}$. \\
\begin{center}
     {\Large$p(x)=\sum{a_{i}x^{i}}=a_{n}\prod(x-\alpha_{i}),
a_{0}a_{n}\neq0,$}
\end{center}

 the root finding problem consist to find
all n root of \textit{p(x)}. the problem of finding a root is
equivalent to the problem of finding a fixed-point. To see this
consider the fixed-point problem of finding the n-dimensional
vector x such that
\begin{center}
$x=g(x).  $
\end{center}
where $g : C^{n}\longrightarrow C^{n}$. Note that we can easily
rewrite this fixed-point problem as a root-finding problem by
setting $f (x) = x-g(x)$ and likewise we can recast the
root-finding problem into a fixed-point problem by setting
\begin{center}
$g(x)= f(x)-x$
\end{center}
Often it will not be possible to solve such nonlinear equation
root-finding problems analytically. When this occurs we turn to
numerical methods to approximate the solution. Generally speaking,
algorithms for solving problems numerically can be divided into
two main groups: direct methods and iterative methods.
\\
 Direct methods exist only for $n \leqslant4$,solved in closed form by G. Cardano
in the mid-16th century. However, N.H. Abel in the early 19th
century showed that polynomials of degree five or more could not
be solved by  directs methods. Since then researchers have
concentrated on numerical (iterative) methods such as the famous
Newton s method, Bernoulli s method of the 18th, and Graeffe s.
With the advent of electronic computers, different methods has
been developed such as the Jenkins-Traub method, Larkin s method,
Muller s method, and several methods for simultaneous
approximation of all the roots, starting with the Durand-Kerner
method:
\begin{center}

$  Z_{i}=Z_{i}-\frac{P(Z_{i})}{\prod_{i\neq j}(z_{i}-z_{j})} $
\end{center}

This formula is mentioned for the first time from Weiestrass [12]
as part of the fundamental theorem of Algebra and is rediscovered
from Ilieff~\cite{Ilief50} [2], Docev [3], Durand [4], Kerner [5].
Another method discovered from Borsch-Supan [6] and also described
and brought in the following form from Ehrlich [7] and
Aberth~\cite{Aberth73}.
\begin{center}

$  Z_{i}=Z_{i}-\frac{1}{{\frac {P'(Z_{i})}
{P(Z_{i})}}-{\sum_{i\neq j}(z_{i}-z_{j})}} $
\end{center}

Aberth, Ehrlich and Farmer-Loizou [10] have proved that the above
method has cubic order of convergence for simple roots.


Iterative methods raise several problem when implemented e.g.
specific sizes of numbers must be used to deal with this
difficulty.Moreover,the convergence time of iterative methods
drastically increase like the degrees of high polynomials. The
parallelization of these algorithms will improve the convergence
time.

Many authors have treated the problem of parallelization of
simultaneous methods. Freeman [13] has tested the DK method, EA
method and another method of the fourth order proposed from Farmer
and Loizou [10],on a 8- processor linear chain, for polynomial of
degree up to 8. The third method often diverges, but the first two
methods have speed-up 5.5 (speed-up=(Time on one processor)/(Time
on p processors)). Later Freeman and Bane [14] consider
asynchronous algorithms, in which each processor continues to
update its approximations even although the latest values of other
$z_i((k))$ have not received from the other processors, in
difference with the synchronous version where it would wait. in
[15]proposed two methods of parallelization for architecture with
shared memory and distributed memory,it able to compute the root
of polynomial degree  10000 on 430 s with only 8 pc and 2
communications per iteration. Compare to the sequential it take
3300 s to obtain the same results.

After this few works discuses this problem until the apparition of
the Compute Unified Device Architecture (CUDA) [19],a parallel
computing platform and a programming model invented by NVIDIA. the
computing ability of GPU has exceeded the counterpart of CPU. It
is a waste of resource to be just a graphics card for GPU.  CUDA
adopts a totally new computing architecture to use the hardware
resources provided by GPU in order to offer a stronger computing
ability to the massive data computing.


Indeed [16]proposed the implementation of the Durand-Kerner method
on GPU (Graphics Processing Unit). The main result prove that a
parallel implementation is 10 times as fast as the sequential
implementation on a single CPU for high degree polynomials that is
greater than about 48000.
\paragraph{}
The mean part of our work is to implement the Aberth method on GPU
and compare it with the Durand Kerner
implementation.................To be continued..................


\section{Aberth method and difficulties}
A cubically convergent iteration method for finding zeros of
polynomials was proposed by O.Aberth[?].The Aberth method is a
purely algebraic derivation.To illustrate the derivation, we let
$w_{i}(z)$ be the product of linear factor $ w_{i}(z)=\prod_{j=1,j
\neq i}^{n} (z-x_{j})$

and rational function $R_{i}(z)$ be the correction term of
Weistrass method (?)
$$R_{i}(z)=\dfrac{p(z)}{w_{i}(Z)} , i=1,2,...,n. $$

Differentiating the rational function $R_{i}(z)$ and applying the
Newton method, we have
$$\dfrac{R_{i}(z)}{R_{i}^{'}(z)}= \dfrac{p(z)}{p^{'}(z)-p(z)\dfrac{w_{i}(z)}{w_{i}^{'}(z)}}= \dfrac{p(z)}{p^{'}(z)-p(z) \sum _{j=1,j \neq i}^{n}\dfrac{1}{z-x_{i}}}, i=1,2,...,n $$
Substituting $x_{j}$ for z we obtain the Aberth iteration method

Let present the means stages of Aberth's method.

\subsection{Polynomials Initialization}
 The initialization of polynomial P(z) with complex coefficients
 are given by:
 $$ p(z)=\sum{a_{i}z^{n-i}}. where a_{n} \neq 0,a_{0}=1, a_{i}\subset C $$


\subsection{Vector $Z^{0)}$ Initialization}

The choice of the initial points $z^{(0)}_{i} , i = 1, . . . , n,$
from which starting the iteration  (2) or (3), is rather delicate
since the number of steps needed by the iterative method to reach
a given approximation strongly depends on it. In [1] the Aberth
iteration is started by selecting n equispaced points on a circle
of center 0 and radius r, where r is an upper bound to the moduli
of the zeros. After[18]  performs this choice by selecting complex
numbers along different circles and relies on the result of [19].

$$\sigma_{0}=\frac{u+v}{2};u=\frac{\sum_{i=1}^{n}u_{i}}{n.max_{i=1}^{n}u_{i}}; v=\frac{\sum_{i=0}^{n-1}v_{i}}{n.min_{i=0}^{n-1}v_{i}};u_{i}=2.|a_{i}|^{\frac{1}{i}}; v_{i}=\frac{|\frac{a_{n}}{a_{i}}|^{\frac{1}{n-i}}}{2} $$

\subsection{Iterative Function Hi}
The operator used with Aberth's method is corresponding to the
following equation which will enable the convergence towards
polynomial solutions, provided all the roots are distinct.

$$ H_{i}(z)=z_{i}-\frac{1}{\frac{P^{'}(z_{i})}{P(z_{i})}-\sum_{j\neq i}{\frac{1}{z_{i}-z_{j}}}} $$

\subsection{Convergence condition}
determines the success of the termination. It consists in stopping
the iterative function $H_{i}(z)$ when the are stable,the method
converge sufficiently:
$$  \forall i \in [1,n]; \frac{z_{i}^{(k)}-z_{i}^{(k-1)}}{z_{i}^{(k)}}< \xi$$

\section{Difficulties and amelioration}
the Aberth method implementation suffer of overflow problems. This
situation occurs, for instance, in the case where a polynomial
having positive coefficients and large degree is computed at a
point $\xi$ where $|\xi| > 1$.Indeed the limited number in the
mantissa of floating takings the computation of P(z) wrong when z
is large. for example $(10^{50}) +1+ (- 10_{50})$ will give result
0 instead of 1 in reality.consequently we can't compute the roots
for large polynomial's degree. This problem was discuss in [17]
for the Durand-Kerner method, the authors propose to use the
logratihm and the exponential of a complex:

$$ \forall(x,y)\in R^{*2}; \ln (x+i.y)=\ln(x^{2}+y^{2}) 2+i.\arcsin(y\sqrt{x^{2}+y^{2}})_{\left] -\pi, \pi\right[ } $$
$$ \forall(x,y)\in R^{*2}; \exp(x+i.y)= \exp(x).\exp(i.y)$$
$$                                       =\exp(x).\cos(y)+i.\exp(x).\sin(y)$$


The application of logarithm can replace any multiplications and
divisions with additions and subtractions; consequently it
manipulates lower absolute values and can be compute the roots for
large polynomial's degree exceed 1000[17].

Applying this solution for the Aberth method we obtain the
iteration function with logarithm:
%%$$ \exp \bigl(  \ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'}))- \ln(1- \exp(\ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'})+\ln\sum_{i\neq j}^{n}\frac{1}{z_{k}-z_{j}})$$

$$ H_{i}(z)=z_{i}^{k}-\exp \left(\ln \left( p(z_{k})\right)-\ln\left(p(z_{k}^{'})\right)- \ln\left(1- \exp\left( \ln (p(z_{k}))-\ln(p(z_{k}^{'}))+\ln \left( \sum_{k\neq j}^{n}\frac{1}{z_{k}-z_{j}}\right)\right) \right) \right)$$



this solution is applying when it is necessary

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


\bibliographystyle{plain}
\bibliography{biblio}
%% \begin{thebibliography}{2}

%% \bibitem [1] {1} O. Aberth, Iteration Methods for Finding


%% all Zeros of a Polynomial Simultaneously, Math. Comput. 27, 122
%% (1973) 339Â344.

%% \bibitem [2] {2} Ilieff, L. (1948-50), On the approximations of Newton, Annual
%% Sofia Univ. 46, 167-171.

%% \bibitem [3] {3} Docev, K. (1962), An alternative method of Newton for
%% simultaneous calculation of all the roots of a given algebraic
%% equation, Phys. Math. J., Bulg. Acad. Sci. 5, 136-139.

%% \bibitem [4]{4} Durand, E. (1960), Solution Numerique des Equations
%% Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une
%% Polynome. Masson, Paris.

%% \bibitem [4]  {4} Aberth, O. (1973), Iterative methods for finding all zeros of
%% a polynomial simultaneously, Math. Comp. 27, 339-344.

%% \bibitem [5] {5} Kerner, I.O. (1966), Ein Gesamtschritteverfahren zur
%% Berechnung der Nullstellen von Polynomen, Numer. Math. 8, 290-294.

%% \bibitem [6]{6} Borch-Supan, W. (1963), A posteriori error for the zeros of
%% polynomials, Numer. Math. 5, 380-398.

%% \bibitem [7] {7} Ehrlich, L. W. (1967), A modified Newton method for
%% polynomials, Comm. Ass. Comput. Mach. 10, 107-108.



%% \bibitem [10] {10}Loizon, G. (1983), Higher-order iteration functions for
%% simultaneously approximating polynomial zeros, Intern. J. Computer
%% Math. 14, 45-58.

%% \bibitem [11]{11} E. Durand, Solutions numÅ½eriques des Å½equations algÅ½ebriques,
%% Tome 1: Equations du type F(X) = 0; Racines dÂun polynÂome,
%% Masson, Paris 1960.

%% \bibitem [12] {12} Weierstrass, K. (1903), Neuer Beweis des Satzes, dass
%% jede ganze rationale function einer veranderlichen dagestellt
%% werden kann als ein product aus linearen functionen derselben
%% veranderlichen, Ges. Werke 3, 251-269.
%% \bibitem [13] {13} Freeman, T. L. (1989), Calculating polynomial zeros on a
%% local memory parallel computer, Parallel Computing 12, 351-358.

%% \bibitem [14] {14} Freeman, T. L., Brankin, R. K. (1990), Asynchronous
%% polynomial zero-finding algorithms, Parallel Computing 17,
%% 673-681.

%% \bibitem [15] {15} RaphaÃ«l,C. FranÃ§ois,S. (2001), Extraction de racines dans des
%% polynÃ´mes creux de degrÃ© Ã©levÃ©. RSRCP (RÃ©seaux et SystÃ¨mes
%% RÃ©partis, Calculateurs ParallÃ¨les), NumÃ©ro thÃ©matique :
%% Algorithmes itÃ©ratifs parallÃ¨les et distribuÃ©s, 13(1):67--81.

%% \bibitem [16]{16} Kahina, G. RaphaÃ«l, C. Abderrahmane, S. A
%% parallel implementation of the Durand-Kerner algorithm for
%% polynomial root-finding on GPU. In INDS 2014, Int. Conf. on
%% advanced Networking, Distributed Systems and Applications, Bejaia,
%% Algeria, pages 53--57, June 2014. IEEE

%% \bibitem [17] {17} Karim Rhofir, François Spies, and Jean-Claude Miellou.
%%Perfectionnements de la méthode asynchrone de Durand-Kerner pour
%%les polynômes complexes. Calculateurs Parallèles, 10(4):449-- 458,
%%1998.
%% \bibitem [18] {18} Bini, D. A. Numerical computation of polynomial zeros by
%%means of Aberths method. Numerical Algorithms 13 (1996), 179
%%200.
%% \bibitem [19] {19} A. Ostrowski, On a Theorem by J.L. Walsh Concerning the Moduli of Roots of Algebraic Equations,
%%Bull. A.M.S., 47 (1941) 742746.
%% \end{thebibliography}
\end{document}
